A huge percentage - arguably a majority - of 3.5 monsters are "puzzle encounters" like that, which challenge/frustrate/destroy parties who don't have the correct answer to the puzzle, and on the opposite end, are trivially easy for a party to deal with if they happen to have access to and knowledge of the correct answer to the puzzle. As I read the OP - and I'll own the reading as my own, and not Endarire's words - DMs who don't expect nearly every encounter to be this way AND expect the party to consistently have a bag full of correct puzzle solutions handy are Doing It Wrong. There's almost an undercurrent of "every person who volunteers to DM for a group must first pass this battery of competency tests" to the OP's sentiment, to my view (and good luck enforcing that).
Indeed, puzzle encounters are practically trivial with the right solutions, but in 3.5 are almost always beatable without(e.g. once you get Big T down to negatives, it is entirely possible to lock him away, with or without Wishes), provided you have luck and plenty of brute force.
In most such cases, the fault tends to lie with the most skilled person at the table, as they are the most able to adjust their play/GMing to fit the group best. The others simply don't have a choice, other than to lean on the stronger person's ability(which is not an option that is universally applicable). Even with someone more capable helping, there are limits.
Broad plot strokes easily abolished by not just individual ability, but with something you can buy(need to cross the kingdom in a hurry? Buy a scroll of Overland Flight to bypass the intervening distance and encounters, or a scroll of Teleport to bypass all the things), can easily wipe out preparation. In fact, such abilities can routinely screw over certain types of groups, where the scenario is predetermined(E.g. skipping the intervening encounters means you arrive at the BBEG's place...two levels too low, and without the plot devices to weaken him).
Offense outstrips defense as well, a skilled(in the optimization sense, which is completely distinct from the DMing sense) DM might make a challenging encounter consisting of high offense creatures(hydras, beholders) attacking from ambush on complex terrain...against a party that is essentially the D&D Iconics is going to flatten them, and they'd be unable to do anything about it. Against a more optimized party it might be down to a coinflip instead, winner takes all.
Emphasis mine. Note that when I brought up similar issues to those emphasized above, a majority of responses put the blame squarely on the DM's (i.e. my) shoulders for not being able to deal with it as smoothly as apparently expected.
and the blame should be there. idic.
so they fly. big deal. that's part of a fantasy world.
unless you have explicitly explained why flight works different / does not work / is harder than normal / or whatever, at some point in your world, the players have ever right to expect that to be how it works and for that to be a clever solution to the problem.
so make the encounters ariel instead of land based. a floating palace of ice, giants living on clouds, or a mysterious portal in the air, or one of the party gets kidnapped by ariel creatures and taken to an eyrie (which can be a dungeon, if that's what you wanted), you can have a storm show up, which if they were wise they would divert around - or become an encounter/adventure in and of itself, or a floating forest blows in, or launches from the ground (it's the season for it) and your goblin encounter just became a race of genasi goblins with glide-skin between their arms and legs (or even use yazarians instead of goblins) and thri-kreen which leap from floating tree to floating tree, or some kingdom takes exception to violations of airspace and nabs them to check for proper visa and travel papers (hey, works just as good in a fantasy world... you could even have the tsa search them for "contraband" or "hazmat" [i'm sorry sir, but transmutation items have known interactions with skycrystals which are common in this area of the world, and cannot be allowed in our airspace; i'm afraid we'll have to confiscate that...] ^^ )
there are so many possibilities for encounters in any environment, that there really is no excuse not to be able to adapt any encounter to a new path the players happen to take.
unless, of course, you've previously established that a particular thing works differently than it is in the books for whatever creative reason (and flight is a core spell / magic effect, its not like it comes from some obscure rule book that you don't have).
be creative. be flexible. adapt. rule of yes. fly with the eagles. generally, it's more fun for everyone. and makes for a more epic, more exotic, more interesting storyline when all is said and done.
and if so many people are basically telling you "You're Doing It Wrong" ™, then maybe you should take it under serious advisement. not that the majority is always right, but on the other hand, there may be something to it.
and hey, not everyone is good at it.
