Return of the Dark Sorcerer

The Phoenix Cave is the same kind of thing where you need to land on a certain mountain tile, it's over on the same continent as where you re-recruit arc. Look for a mountain range that looks like a humanoid kind of shape and land on the head. There's an NPC somewhere that mentions this hint, but it's easy to miss.