I posted the exact same question on gamefaqs, and someone suggested I leave and re-enter to get a new pool of permutations, but that hasn't worked for me. I still get Mysidia-->Dwarfen Colony and Earth Tunnels-->Lost Souls way more than 1/128 times. I'm going to try to exit and re-enter every time I load instead of doing it once and saving my game and loading repeatedly.