Reading through the proposed checks-and-balances, and the differences of opinion, I'm starting to wonder how many if, dare I say, any limitations are really needed. I've dealt with Paragon PCs that can fly, and though they do have certain advantages, I'm not sure it was ever so imbalanced it ruined the game.
I can't think of quite so many encounter breakers as I originally assumed. I mean even in an open field with the sky being the limit, the rest of most parties are earthbound, and I'd call the encounter lost if everyone on the ground dies and the pixie is left. If he or she flies off in retreat, is that so bad? For the OP's group, maybe they're perfectly built for such encounters, and the DM will have to provide varied terrains, some indoors, some with strong winds, some with flying enemies, but some, yes, where flight gives the overriding edge too.
There is also an innate power range limit. The pixie will have to be at least 20 squares away from intended enemies, and there are monsters (albeit not nearly as many as range 10 attacks and melee) who could reach, never mind possessing flight themselves.
Yeah, I wouldn't be too discouraged with the notion unlimited flight provides its own many advantages, or how do you guys feel about some sort of super gamist 'There can only be 1 of said race in a party' for Tiny and Large creatures. Hehe, on second thought, I think that'd spur more rage than altitude limit.