Can't everyone here agree to disagree? The issue is subject to interpretation, and I'm perfectly content to have each DM rule as he sees fit (the rules can be viewed as supporting them either way).
If you are playing in an RPGA game (or otherwise try to follow the FAQ for consistency of player expectations) then the 3.0 FAQ clarification might be your primary choice (I'm not aware of any change in 3.5 that would invalidate it). It says:
"Can a creature fly underwater? I’ve never heard of a
normal bird flying underwater. What are the rules
regarding this? If it’s possible, what is the penalty to
movement and maneuverability?
Flying creatures must swim when they enter the water, just
as other creatures do. A fly spell lets you swim at your normal
flying speed, but with the same maneuverability as other
swimmers (perfect maneuverability). Incorporeal creatures also
can fly/swim in this manner (they move through water just as
easily as they move through other substances). Note that
gaseous creatures cannot enter water."
I personally would combine this with the MotP ruling, so that winged flyers can't fly underwater, and wingless/magical flyers do so at reduced speed (maneuverability doesn't seem like it would be an issue underwater). Is that unreasonable?
As for Superman flying underwater being relevant... well, this is a fantasy game, and using fictional wingless flying examples from literary sources seems perfectly reasonable.