If you've got a druid or a UMD user, Animal Growth on a flying animal would also solve the issue, as would riding an elephant and giving it flying somehow.
The MMII has the warbeast template, which allows a vermin or animal to be used as a mount, and gives some excellent bonuses as well. It also lists the price of a wartrained animal based on HD (and they are dirt cheap), so if you can find a flying animal you like (dire eagles from Races of Stone are pretty good), and can purchase an advanced version that's huge, that would work too. A warbeast roc, for example, would cost 1,525 gold, and also have several stat bonuses as well.