Well, at some point in 1992, Phantasy Star IV was going to be a completely different game than it turned out to be.
Phantasy Star IV: The Return of Alis - It seemed to be a different story. Interestingly, there were two versions of it planned, a 12 megabit cartridge and a CD version.
Look at the third page (GamePro magazine July '92)
http://www.ign.com/games/phantasy-star-iv-the-return-of-alis/sega-cd-816198Then also in 1992, Sega showed characters and story scenes for, not Return of Alis on CD-ROM or cart, but the Phantasy Star that would later be titled End of the Millennium.
The Phantasy Star Compendium book also mentions (IIRC) Phantasy Star IV starting out on CD, but production was canceled.
So, what about a
Phantasy Star V ? Well, Sega probably has plenty of material to work with, though I just don't see it happening with how Sega is, presently, as a company.