In the "no political restrictions" worlds, you can open terminals anywhere in the world. You spend more money but at least you can get in to any airport.
In the "Realistic" worlds, my strategy is to go for the foreign routes first as much as possible. So if I'm based in the U.S. for example, routes to Canada, South America, Asia & Europe are more of a priority than US domestic routes. By the time I get back to them, even if all the gates are taken, I can always build terminals anywhere in the US. Those that focus on the domestic routes first tend to end up in your situation - all dressed up & nowhere else to go.
Playing as Australian Airlines, you'd probably have to do the Aussie domestic routes first to generate the cash to get the longer range aircraft to reach the rest of the world. And as you say, by then, a lot of the gates are gone.
The other option is to play the "no airline limit" game worlds. In these, I'll have one "main" airline, & a dozen others operating all over the world, which serve purely as "gatekeepers". When my main airline is ready to fly there, I can close routes & return a gate in one of the other airlines. It then becomes instantly available, & if I'm quick, I log out of that airline, log into the main one & grab the gate (before someone else does!). Eventually, gate by gate, all the other airlines of mine will be shut down, leaving one big global airline.
Well, I've just given away all my strategies. I hope not too many people read this.