Two words: TIME TRAVEL. There are many ways around story points if you think about it. I mean Fenrir is dead at the start of the story, but can be brought back to life. So why should it be any different for the the embodiment of Rebirth? If you want to make it harder why not have the Eyes of (Insert Element) from Waking the Beast, Whisper of the Moon, Whisper of Dreams, and if you want to get real crazy throw in a Carbuncle's Ruby; All of which will be required to open the battle field. Travel back to some battle field in Wings of the Goddess or Travel to Castle Zvahl Keep (The Crossroad of Fate). I mean, let's be honest... It's a fantasy game, ANY thing is possible. Heck, Why not fight Phoenix in some place in Abyssea.