Currently the Prince, Princess, and Queen Klaknak are spawning in Kith. In classic, they spawned in MT (and I do not think they were moved to Kith until much later, like 2007).
The initial Alla's entry for princess has notes going back to 2000.
http://everquest.allakhazam.com/db/npc.html?id=2101
Posts about the Princess (I take this to indicate she is on the Klaknak worker spawn cycle)
http://web.archive.org/web/200012161...2101&mid=16437
Posts about the Queen in the misty thicket Beastiary.
http://web.archive.org/web/200012111...ne=7&mid=15799