Map of 600 ADMap of 12,000 BC after the Ocean PalaceMap of 12,000 BC before the Ocean PalaceThe "before the crash" one was interesting. I never realize that Mt. Woe was on the western half of the 12,000 BC map. Judging by the position in which it fell, it probably became the Pt. Vortex area.
Magus' castle would have been on a landform directly above where the Ocean Palace was situated. I suppose this makes sense, given that that's where he summoned him, but it seems weird to me that the Ocean Palace and Magus' castle are situated to the northwest of where Lavos crashed into the earth.
In any event, the water-level of the place where it fell in both the Before and After picture are fairly shallow, and there are plenty of small isolated landmasses. It's not impossible that they island hopped and survived until the Guardians and Porreans ran them off.
Interesting point: We're led by Melchior's arrival in 1000 AD Medina to believe that Janus arrived in the Truce Canyon gate area, where he was met by Ozzie, who tried to ambush him. What happens between then and 600 AD when Magus attempts to summon Lavos is up to debate, but at least a few things can be agreed upon: Magus became leader of the Mystics, probably through his skill with magic, built a fort where his castle is, and where the ruins of the Ocean Palace lied.
None of the monsters in Truce Canyon can use magic, but the ones that serve in Magus' army can. I'm starting to really favor the "Magus gave the Mystics magic" argument.