Good News from the MMII
Humanoids:
*Abeil (vasal) - fly 60 (average), 2 claw+sting
*Boggle - small size, +2 natural armor, climb 30', 15' reach (does this even qualify?), +10 escape artist, 2 claw+bite
*Thri-keen - +3 natural armor, speed 40, 4 claws+bite, deflect arrows, +4 hide in sandy settings
*Yak-folk - +7 natural armor, large size, 10' reach,
Outsiders:
*Bladeling - +4 natural armor (and freaky looking)
*Cervidal (celestial) - +4 natural armor, 3 natual attacks (slams and butt)
*Abyssal Maw (demon) - +5 natural armor, bite for 2d8
*Abyssal Skulker (demon) - +2 natural armor, speed 40, 2 claws
*Abyssal Ravager (demon) - +4 natural armor, speed 50, sting
*Jovoc (demon) - small (+1 AC/attack), +3 natural armor, 2 claws+bite
*Avsespa (devil) - +7 natural armor, fly 40(good), 4 claws+sting
*Planetouched - nothing worth note
*Sylph - small, fly 90 (good)
By MMII, you can fly no matter what your type.