While I don't agree that it has to be flight and teleportation, I do agree that any CR 11+ creature worth it's CR needs responses to the normal sorts of strategies that high level characters might employ, including flight, invisibility, save or suck, etc.
Flight can be countered in several ways:
a) A sufficiently long ranged attack that you can respond to death from above or at least reduce its efficiency to a level that becomes trivial. If you decide to fly and it beans you with a rock for 4d6+18 damage, then it stops looking so great. If the characters have to fly a mile over the target, the number of hits they are going to make practicing high altitude bombing makes it very resource inefficient to try to take it on that way, especially if it regenerates.
b) Less long ranged attack, but ensuring that the creature is always encountered in an sufficiently small area - a cave for example - that you can't take cover simply by getting out of range. With a sufficiently small enclosure, the creature can rely on melee and possibly jump.
c) Giving the creature a burrowing speed, which thereby creates an impasse. Alternately, giving it the amphibious trait and placing it near to water can create a similar impasse.
d) Giving the creature flight, or allowing the creature to summon things that can fly.
e) Giving the creature various immunities and resistances to ranged attacks, such as with Weather Control or the ability to create suitable concealment for itself (clouds of fog, etc.), or the ability to catch/deflect missiles, etc.
Invisibility also needs a counter. In general, the above sample troll has scent and high listen and spot so it has minimally sufficient ability to counter invisibility, but probably not flight + improved invisibility (plus say a 10HD wand of fireballs). If you are really worried about that and your party tends to optimization, all the above suggestions plus rolling in the elite and replacing the fiendish with the Half-Fiend template produces a reasonably effective CR 17 monster.
But yes, flight is the reason the CR of a simple brute sort of creature has to be effectively capped.