I have two people who can cast Ultima. Setzer (don't ask why) and Celes. Terra has Ragnorock right now. I took Locke to explore Narshe pretty early on and just beat Hidon and beat Cultists Tower (my guess is in the other version fanatics tower?). Every character is level 40. I guess I just need to find Deathgaze again and hopes he doesn't flee and do the Odin and Doma side-quests.