I think Melchior was first sent to that mountain (in dark ages) for defying the Queen , warning her about the problems that comes by messing with Lavos, we than save him (but we already knew him in the present) , when Lavos awakes everybody is scattered in different timelines , Melchior goes to Medina (present), we are presented to him some time latter his arrival. Probably in the original timeline we never rescue him, but maybe the other sages or Schala saves him, that goes to stop Lavos and is sent back in time (thus the Melchior we originally saw didn't know about us, just like the king of guardia didn't knew about the Rainbow Shell).
It is just like Magus/Janus coexisting in dark ages... Janus will be sent to the middle ages and becomes the fiend messiah Magus, that tries to summon Lavos to kill it, just to be sent again in a gate to the Dark ages.