Playing FFTactics (thus knowing Ultima's Zodiac Sign is Virgo) and having some knowledge of astrology made it pretty easy to track her down. I think I had a harder time reaching the actual story conclusion than finding Ultima and Omega Weapon. I also lucked out and got the Ultima Sword while I was there without having to deal with the stupid respawning chest, not so lucky with the upgraded Shield...