As far as I'm aware, listen checks did not allow you to determine the location of a hidden/invisible creature in 3e, only their presence (ie., you hear breathing; you're pretty sure there's someone hiding or invisible nearby). Only a spot check could pinpoint the square a hidden target was in (AFAIK). At least in our games, Improved Invisibility + Fly was a very hard combination to beat. Just cast and move; you were almost impossible to pinpoint, and practically invulnerable even before the 50% miss chance. Toss in Silent Spell and you didn't even have to move.
You could use a Listen check to determine approximate distance and direction of a creature. That's good enough with enough of a check to determine distance.
And I don't recall 'Fly' being an automatically silent form of transportation, but that's personal preference really. The description doesn't mention silence in any form.
It doesn't make sense to me that an invisible creature would be so easy to detect unless there were some consistent, minimal, visual trace.
He's not so easy to detect. He has total concealment, which means any time he spends any move action he can go Hidden. This costs him nothing to do, and is only broken if he attacks, or is not silent, or an attempt is made for him and another creature to occupy the same space. These are all trivial things to do.
Most mages don't wear clod stompers, so their footsteps won't necessarily be easy to detect in the midst of a noisy battle.
That's why characters in leather or cloth get no penalty to their stealth checks that, as noted above, they get to make as part of their move action automatically when invisible.
Not every battlefield can be so heavy with dust that it leaves footprints (the King's anteroom will likely be quite clean, for example). Given the convenience of cantrips, it's unlikely that the average wizard will smell so bad as to give away his position. If the mage avoids walking near anyone, they can't feel him brush past or stir the air.
And if he's trying not to give away his position, chances are he is being quiet. And if he is, he makes his stealth check.
Either he's making his stealth check, or he is not. And if he's making stealth checks, he's trying not to be noticed. And if he is not, then he is NOT trying not to be noticed. There's no middle ground here.
Yet it isn't very easy for an invisible Wizard to move about undetected (particularly without Stealth Training). In 3e, invisible creatures received enormous Hide bonuses ranging from +20 to +40! In 4e, there's no bonus beyond the capability to become hidden.
The capacity to become hidden -anywhere- at -anytime- provided you meat the requirements. Meaning not needed terrain. That's -huge-. And it's not difficult to be undetected. It's just not perfect. The wizard who is using invisibility regularly would probably have Stealth Training. He's clearly wanting to be undetected, so he'd take training in the skill that bolsters his non-detection. He could even fluff it as magics that pad his footsteps, etc.
Don't get me wrong, that's how I think it ought to be. It's just that, IMO, the mechanical change makes the most sense when accompanied with a fluff alteration (invisibility is no longer a perfect visual obfuscation).
I find accepting the fact that invisibility means 'You are unseen' to be completely acceptable. I've always found the reliance of invisibility to mean 'undetectable' to be a complete crock, so the new rules actually make -more- sense to me. Invisibility is -still- damn powerful, it's just not 'autowin' and requires a little bit more effort on the part of the player. Or rather, SOME effort.
If the above doesn't disconcert you then, as I said before, think of it as you will. I wasn't suggesting that mine was an official response. It is merely my own interpretation, offered in the possibility that it might be helpful to someone.
Fair enough.
But regardless, one thing to consider.
You have the exact same chance to make your stealth check if you are invisibile as you'd get if you were completely hidden behind a brick wall.
In both cases, you cannot be seen.
Think about that.