We didn't have flight in queldanas or however you spell it. It's honestly not a new thing.
Flying only existed in Outland during BC. Quel'danas was built during BC, and was part of the vanilla no-flying areas, even if it was instanced off the belf capital. Which was also a no flying zone, since the capital was "connected" to Azeroth (Eversong and Ghostwoods), same with the Space Monkey area. Though even if you could fly in Outland, it wasn't that convenient, since the land mass was soooooo fucking huge, and not often were you blocked by high walls on the ground.
Remember how Dalaran used to be no flight? You could fly into it, but it would dismount you if you got too close to the ground, and you couldn't mount and fly out unless you were on Krasus landing? From a fantasy perspective, "northern winds" was a reasonable excuse for no flying in Northrend, but the high gold price was a terrible means of obtaining it if they were being true to the fantasy.
Cataclysm made the rest of Azeroth flyable, except monkey island and belf areas.
Same thing in Mists as it was in Wrath - "can't see through the mists", but again, they failed the fantasy by putting it behind gold and max level.
Warlords just told us to go fuck ourselves with flying, and forced you on the ground for no reason. They put in 1000 flight points, but two flight points could be close and blocked off from each other on the ground entirely. And even with no flying, Draenor still felt half the size of Outland.
Legion, they doubled down on the go fuck yourself, but then made flying not that important - except for Broken Shore, which is literally the biggest pile of shit they've released for content in a long time.