I have to side with Irda Ranger on this, and though IR was tactful, I'm going to say this a little more forcefully (because I'm generally not tactful).
There is a vast difference between challenging your players and punishing your players. Many of the suggestions provided are unreaasonable, sadistic, cruel, unfair, arbitrary, and designed to kill enjoyment, not promote it. They bear all the hall marks of bad DMing. They suggest that the sessions have become adversarial DM vs. the Players, that the DM is having a hard time controlling his campaign, and that the DM enjoys stroking his own ego by showing how much more devious and cruel he can be in a contest that 1) isn't a contest and 2) isn't even remotely a fair contest and 3) isn't being run remotely fair by the referee even if it was.
Nowhere did RM suggest his campaign was out of control. He merely suggested that he was running out of original ways to challenge a player with a quite extraordinary ability - flight. The problem is of course, that there are a very limited number of things that specifically challenge flying creatures and you are better off focusing on original challenges for players in general (and there are arguably a limited number of those).
"Maybe make them make a check every so often to see if they can still keep flapping their wings amongst all the branches."
Do you make your PC's make a check every so often to see if they manage not to trip over the roots? Generally, either you should rule that either there is room to fly from A to B for a creature of a given flight manueverability or there isn't. Both are reasonable rulings depending on the type of forest, provided that you don't always rule that there isn't room when it would be particularly useful to the player for there to be flight room. Making arbitrary and onerous house rules to push perfectly reasonable activities isn't.
On the other hand, encounters with dangerous arboreal creatures in a fantasy forest or hitting a spider web designed to catch flying creatures are perfectly reasonable provided they don't happen every time the PC takes off the ground.
"He's always the first target selected by the enemy."
It wouldn't be entirely unreasonable for foes to attack him first just because he flies and is obviously attention getting, just as it wouldn't be entirely unreasonable for foes to flee just because he flies. But there are several problems with this. One, you are punishing the player. Two, you aren't necessarily playing the monsters intelligently. If the monsters _are_ unintelligent, fine, attack (or flee from or surrender to) the flashy target. But if the monsters are intelligent, attack the dangerous target - like his wizard friend. The point is, your choice of target as a DM should never be based on metagaming. You should be above that.
"When's molting season for a half-celestial. It's got to be at least once per year and should take several days for the new feathers to become air-worthy."
Why does it 'got to be anything'. There is nothing to suggest that angels molt regularly. Celestials are not avians. Regular molting might be a welcome background aspect of a avian character - say an Aarakroka - and could be developed into a memorable RPing experience. Celestials molting for any reason short of an alignment change or similar cosmic reason is dumb and pays a unworthy ammount of attention to what it means to be celestial. If an Angel loses his wings (or even a SINGLE feather), he has more problems than a need for new flight material. If I were running a half-celestial, I would use the atmospheric of having a feather fall out as a warning that he was straying from his alignment principals. Molting would be a prelude to metamorphasis into a half-fiend. Any other use of molting in a celestial ought to be equally well thought out and tied intimately to the campaign concept, not some arbitrary reason to punish a player.
"Have a villian capture him and pluck his feathers?"
Ahh, now that's a great suggestion. Sure, take away your player's characters. You'll stay a DM for a long time. I'd suggest never doing anything so overtly brutal to a player without some sort of implicit consent from the player. In otherwords, make sure that your actions agrees with the player's sense of story. Don't maim, rape, alignment change, mind rape or otherwise torture the character unless the player agrees that this is an interesting and reasonable out growth of his own choices. And by the way, this goes for killing a character to.
"If the PC actually uses the wings to fly, it would be a great strain thus limit him to five minutes a day per constitution point if he's just normally flying from point A to point B."
It is reasonable to assume that thier are limits on how long a particular creature can fly per day, but 5 minutes per point of CON probably isn't a reasonable assumption. I would suggest that average birds, who haven't as much manueverability and don't have supernatural sources of power, can probably fly more than an hour (total) in a day - and that manuevarble and healthy birds can fly pretty much all day long. I'd assume that a healthy half-celestial can fly as well and as long as an eagle or condor, and is as manuevable (as the rules indeed suggest) as a hummingbird. I'd assume that most players that chose to be half-celestials would assume (based on the rules and their perception of the appearance of such a being) much the same thing, and I see no reason to disappoint them. So something along the lines of an hour per point of CON, half that if he is doing alot of high energy manuevering like hovering and flying down dungeon corridors. On the subject, it wouldn't be unreasonable to assume that flying creatures who aren't fully celestial need to consume very healthy quanities of food to power themselves - as long as you don't take this to extreme and insist that players eat 50 times thier own body weights just because 'hummingbirds do'.
"Force him to take additional feats, skill points in order to effectively use those wings in combat maneuvers. Fly-by-attack, airbourne combat, etc."
Well, yeah. But he's probably going to want to do those things anyway, and if he doesn't, don't force him. It is his character.
"Constantly have small avians dive attack him from the back."
Why? I admit I've often spent an hour watching a hawk get chased about and worried by various small manuevable nesting birds. It's quite amusing, and interesting instruction in aerial combat, but to do this constantly is just irratating and again arbitrary.
"If he asks why: the bird-god drove them to it to punish the interloper."
Oh sure. The bird god just hates flying things. Did you ever consider that maybe the 'bird god' is this guys patron?
"My players learned long ago, better to play a mistructed tiefling than a beloved celestial."
Sounds like you are in the camp of 'Evil is better than Good'. How tiresome.
"Of course, that one dragon with level adjustments for lots of races moved 1/2 celestials to a +5 Level Adjustment, IIRC."
Did they? Good. That's closer to fair. Too late now though.
"if he ever gets caught in a nasty trap in a dungeon I could see a flying character developing a nasty case of clausterphobia"
Probably no more so than anyone caught in a nasty trap in a dungeon. Unless the player put claustraphobia in his character concept, why assume he is prone to panicing or cowardice?