I'm not saying you should automatically deduct ECL 3 or 4 from everyone who rolls Pixie, just like you wouldn't add 10 levels if someone became an earthworm (hmm... it's Earthworm Jim!). There has to be a level of common sense involved here. The thing is, though, while the big Half-Ogre Barbarian would lose a lot of power by turning into a Pixie (cuz a Pixie Barbarian just isn't that impressive, except maybe to other Pixies), the Human Sorcerer WOULD see an improvement. So would the Halfling Rogue (9d6 Sneak Attack is still just as damaging when caused by a 1d2 weapon instead of a 1d4, and now I can hide better and can fly, with a better attack roll and AC?)
On the other hand, turn the Sorcerer into a race with no hands (say, a panther) and he's really neutered, while the Rogue still does fine as a big cat. The Barbarian will do okay as a panther, although he'll have to do without his old weapons and armor. So, it varies by your character classes. A Psion does great turned into something without hands, since he doesn't need to gesture. It's all relative.
The problem for me is, at high level I've seen people use Reincarnate like they use Polymorph Other: to permanently give themselves a really useful form. Sure, it might take a few tries, but eventually you'll get something with useful abilities. It's stupid, but it happens, especially for those classes that don't really care about their physical form (most spellcasters).
AFAIK, the concept of reincarnation in the real world assumes your soul transfers but your mind doesn't; a person reincarnated into a cow isn't intelligent. So, we're already accepting that D&D uses an alternate definition; why not expand it further, and just give all those creatures opposable thumbs? Sure, you're a badger, but you're a badger with a sword!
The easy solution would just be to change the table to only include ECL 0, equipment-wearing, opposable-thumb-using races, so that all classes are affected equally. It's boring, but it's balanced.
IMC, when this has come up (a couple times, once giving a good race and once giving a bad one), I've sat down with the player involved, and we basically re-made the character in the new race, trading some unusable Feats for ones useful in his new form, shifting skill points around, and even trading some class levels, so that in the end he wasn't suddenly more or less powerful than the others. It was a good amount of work, but I already do this sort of thing for PrCs.
IMO, unless they're a Druid or Ranger or something, no one should WANT to be Reincarnated.