There is an assumption that the Titans left. What if they didn't?
The Titans left Azeroth to the care of the dragonflights, but what if they never truely trusted the dragonflights.
The Maps are all Titan Maps, or those that where created by 'man' from what they discovered. But assuming the Titans never wanted to be found why not remove their continent from the maps.
In removing the continent 'man' will not seek to discover the new continent like northrend or pandaria, they only need to be concerned of vessels lost at sea and deal with them to remain lost (either killing the crews or fobidding them to leave)
Potentially you can have an Alliance ship leaving Darnassus to SW (one of the few ships that even minutely goes in that direct) gets blown off course. The crew see an unfamiliar skyline, and unlike the crews before opt to turn away than go to discover it. On returning to Darnassus the Captain reports to Stormwind of his discovery. The Alliance move to form a fleet to discover this land, Horde spies learn of the fleet but unaware of why, build one themselves to stalk the Alliance fleet.
It could be that the continent is a Titan's garrison, ready to protect or repair the world if the Dragonflights fail.
1) During the Cataclysm you could of had the Shattering break an Old God's prison, requiring the titans to deal with the greater threat. Due to the distraction this is the reason the alliance ship managed to escape rather than be dealt with.
During the time of the Cataclysm and Mists, the Old God has managed to corrupt titans and natives creating the enemies.
2) A filler expansion, the Titan Island had already been discovered by the Naga. The early zone and raids are based on aiding the few remaining titans in reclaiming the Island, Future raids can be designed as an offensive, cleansing Naga invested Islands one after another with either Azshara the final boss or a one of her commanders.
This is the potential to go into two distinct expansion:
a) Assuming that Azshara was not the final boss, it may be a case of the reclaim of Islands have caused Nazajatar to be located allowing us to attack it and kill Azshara.
b) Why did the Naga attack? Have the Titan Garrison be the entry into the Old God's Prison, have effectively a Continent sized Deepholm, a continent underground. The Cataclysm cracked the defenses, it wasn't enough to allow them to escape by enough for them to command Azshara to free them since they helped her.