I understand the problem you r having with flight... but considering the other spells available (f.e. invisibility, dimension door, ...) it isn't too bad.
Yes, it often is kind of strange to have a fighter fly around... if you play on a world like f.e. Middle Earth... no one could fly there... but then, magic on Middle Earth is IMO just different to f.e. Forgotten Realms.
Next is, a Monster CR is based on the idea that the heroes are probably at some point able to fly... try fighting a dragon if you cannot... (my group just tried at got nearly eaten).
What you could do is make flying a skill. This makes flying a bit more difficult - especially during a fight. You could take the ride-skill to give you ideas about DCs.
something like:
fly basic speed (60ft/40ft) - DC 5.
keep flying while being hit - DC 5 + damage taken.
basic attacking while flying - DC 10.
full attacking while flying - DC 15.
Casting a spell while flying - Concentration DC 10 + spell level.
a creature with a fly speed (built in, natural) gets a +8 on all these skill rolls automatically.
last thing would be (IMO) to add a fly skill to every creature you use... I would do so, depending on their maneuverability... a good flyer has +15, a poor flyer has only +5... something like that...
you should also consider natural surrounding... a nice wind can heighten fly-check-DCs by +5...
I would make the fly-skill a class-skill vor everyone able to cast the fly-spell... everyone else is cross-classing...
I am pretty sure that this would reduce the amount people fly around in battle by a good amount...
You can also consider to make meele weapons do only 1/2 str-damage when flying, since you just push yourself away from your opponent because you have nothing to hold against when flying (but you should do this for your creatures as well)...
about allways flying... well 60ft/rd is equivalent to 6mph... maybe any wind stronger than 6 mph will make you move where the wind is blowing and not where you want to go... have a strong wind suddenly blow away all the flying characters... those survivors will think twice in the future before they take to the air again... large and larger creatures with wings and the hover-feat can probably just blow them away as well... maybe even herding them somehow...
next question is the stealth-question... when flying you are unable to hide. Full Stop.
Therefore, when moving around, anyone on the floor would get a hide check vs. you spot check and if you miss the spot he can attack you (and all of his buddies). Rember also, that a rogue can use a missle weapon to sneak attack if it's less than 30 ft away... When flying, you will be seen for miles - often before you even have a chance to spot the enemy... not ideal IMO.
and last, there is allways the nice basic trap ... a pit trap with poisonous spears at the bottom and an antimagic field above... but this is kind of crude...
But basically I can understand your problem and am having similar problems... what good is it if you build a castle if everyone with fly, spider climb, invisibility, levitation, dimension door etc etc can just come and walk inside? - I personally have f.e. much more problem with the spell Wind Walk... since you can avoid much much more obstacles that way (and it is much faster, has a much longer duration and it works on whole groups at once and and and).
On one side you really have to give some rewards to the players... the standard knight inside his standard castle shouldn't be much of problem at 8th level anymore... IMO the player should feel every once in a while that they are now at a point where they really are powerful - more powerful than many others in the world...
...but when it comes to the main-villain...
For one thing - this villain is certainly aware, that there are creatures out there that can fly (and make themselves invisible and can teleport and and...). Therefore he will do his best to protect himself (and if possible his mansion) from these foes as well as from others...
...next, he is very likely to hear about the PCs before they arrive... many villains are incredibly smart... one smart thing he can do is sending him some moderate powerful cannonfodder and have a look at their tactics (through spys, divinination, speak with the dead later on... whatever) - there he would find out about if they do flight very much to their advantage...
...and here is just a short list of the ways he could prepare for that:
- Dispel magic is allways nice to maybe have even additional buff-spells disappear...
- maybe cast "Black tentacles" at the ceiling... reach isn't enough to attack creatures on the ground... but those flying?
- buildings can be secured by spells like forbiddance... flying doesn't help there...
- dispel magic can be built inside a unhallow spell...
- you can set all kinds of traps up for flying characters - if you know, that they r the only flyers... starting with simple razor-wire or scythe-blade traps... swinging block-traps, net-traps, ending in glyphs and spells like fireball that can only be seen/are triggered once someone moves above 10 ft...
- he could also go for the fact, that he needs "air superiority"... casting air walk, fly or levitate on his own minions (and himself), summoning flying creatures etc...
- spiders and other creatures that can fling webs are allso allways nice vs flyers
- take a gust of wind-spell... blow them away... through some doorway and imprison them using a wall of force... or just make the gust of wind-spell permanent... try to fly through this

- blow them out of a tower - and have someone large waiting outside... blow them through a portal into another dimension....
there are supposed to be even more "flying-rules" including flying-check DCs in the dragonlance campaign-setting - but since I don't own the book I don't know if these would help...
...but I hope to have given you some ideas at least