Very hard, says Drysc. First off, they'd have to fix the tops of mountains and such that can't currently be seen (which, admittedly, I realized when I first learned about flying mounts). But then they'd have to make sure all of those locations matched what was supposed to be there-- if you actually flew up to see Nef's balcony, you'd have to see Nef sitting there. And they'd also have to completely finish Mount Hyjal and all the other currently non accessible zones, including every building and town that's supposed to be there, because of the lore. By the time you get to whether players should be able to fly from one continent to another with or without a loading screen, you're talking, as Drysc says, about completely reworking the server architecture, and we all know how good Blizzard is with changing server architecture.
I don't mean to defend Blizzard-- someday I do want to swoop down low on my Nether Drake over the Barrens as lowbies run and cower in fear at my epic-ness. But I can see why that wouldn't happen for a good long while. More importantly, I can't wait to be impressed by what they have done-- all of those problems will (we hope) be solved in Outland, where everything's been built from the ground up (literally) to be explored by flying mounts aplenty.