Outland > Northrend > 1-60 Azeroth > 80-85 Azeroth
From what I gathered, Blizzard devs were also looking at ways they wanted to fix this particular inconsistency. This storyline inconsistency might remove immersion for the player and seems to lose the focus of the overall story arc of Cataclysm. However, I had a suggestion in mind.
One easy, though somewhat cheap fix, would be to place two portals in the Caverns of Time. One for the Outlands and one for Northrend. When players hit level 58, a particular questgiver(for my example I'll call him Tom) in one of the main cities (in my example I'll use Orgrimmar and Stormwind) would ask the player to head to these portals to travel back in time to help subdue this new danger. Also, a portal to the Caverns of Time would be placed in both Orgrimmar and Stormwind for easy access to the two portals.
Apart from the quests that the player would take part in the Outlands, Blizzard can create one central storyline quest chain dealing with the overall problem that the player was asked to fix by Tom. Obviously this questline is optional, but it would give focus and reasoning as to why the player went back in time and would give a returning player something new to do while in the Outlands without having to recreate the whole zone. Maybe this questline can give some insight, or help deter the current cataclysm happening in the present. This way, the player doesn't feel like he's thrown out too far out of the picture of what's currently going on in the present time and helps keep a bit of immersion.
So, having said that, what happens to the Outlands and Northrend as they stand now? Well, for the time being, while Blizzard is either busy with current Azeroth or rebuilding Outlands/Northrend, they could block all passage to both zones. Maybe you could have the Shattering Sun Offensive or some other faction in Outlands decides to guard the portal to keep any possible Twilight cultists from spreading into the Outlands. This does include the player so they won't be able to enter. Northrend travel could be blocked off as a means of the Argent Crusade not needing any more troops for the time being in clearing off the Scourge in Northrend. Eventually, when Blizzard is ready, we can see these two areas in its' current timeline glory, possibly with an in-game event leading to our revisit.
So what happens to the quests that involve travel to the Outlands? Example being the quest chain involving Tirion trying to save that guy in Icecrown. Well, I'd suggest Blizzard tries to keep from creating quests that require the player to go there, but if necessary, they could phase it somehow and attempt to not make it too awkward looking. This would be most important in its' presentation.
Though I'm sure Blizz has already given thought to some of my ideas, maybe they'll find something of interest that they could implement that they may have passed over in the possible case that they do come across this topic.