What about the world locations?
Broken Sepulcher: That big island in the south? Keeps him from overruning civilisations too easily
Dragon Bones: Could be anywhere really. Perhaps in Malakim lands? (the whole 'bleached bone' thing).
Letum Frigus: Was the west of the Illians in AoI
The Maelstrom: Put it in the western ocean, so there's something there?
Odio's Prison: Says 'the Lands of Kilmorph' in the civilopedia entry, I guess that would be Khazad turf.
Pool of Tears: Elohim, as already mentioned
The Pyre Seraphic: Smack right between Bannor and Clan lands, give 'em something to fight over
Remnants of Patria: Tough one. I think perhaps around the area of either Elohim of Kuriotates? Maybe Amurites?
Tomb of Sucellus: No idea. The southeast (as there's nothing there yet)?
Edit: Tomb of Sucellus is buildable by Amurites in age of Ice, so it should presumably be in Amurite lands.
Yggdrasil: Elf lands, between Ljosalfar and Svartalfar to cause similar issues as Pyre Seraphic.