Well, the Medina area from 600 to 1000 saw the departure of Magus, so maybe that had something to do with it as well? Especially with Lavos sucking his whole castle into a time portal, assuming that's what happened. (?)
I think Melchior was there because it was convenient to have him there at the point of the story.
Now here's a question: the Mystics were around in 600, and 1000... but not 2300. Were they still around in 1999? If so, was Lavos's emergence what killed them off? If they still stuck to the same parts of the world, that could make sense. But it seems like magical kinds of creatures (monsters?) should only exist in past times, not present/future-y times. So, with the exception of an occasional Nu, seems to me they shouldn't be around anymore.
But what do I know.