Perhaps you've gone through the CB and seen the Mounts section in the shop? Well, that's not the half of it, my friend! There are many creatures that have Mount powers and thusly are valid mounts for you, but are not listed in the CB, as it currently only sources those listed in the Adventurer's Vault. I will list those first, then provide a second section, organised by source material, of other creatures. (I considered putting them all in alphabetically, but breaking it up makes it a bit easier to read.) Please also note that the CB's listing of these creatures stat blocks is woefully inadequately formatted in places. I will provide the compendium link where I can for the relevant critter, for proper referencing of their capabilties. Also listed is the creatures lvl, and if it has the Soldier role, which is relevant for the Barding items (See under Mount Items). If a creatures stat block has been errataed from what is in the printed books, I endeavour to list the differences, if they relate to it's use as a mount.
A word to DMs: Some mounts are very, VERY powerful in their capabilities, especially when added to everything else a player can do, for example some of those from the Draconomicons. Make sure you know what your players are asking for when they say 'I want THAT one for a mount!'
Flight capabilities: It may seem there there is little difference between a mount that can fly and one that can fly (hover). The reason I prefer flight with hover over those that lack it is because of what happens when you're stunned. A hovering mount will still fly. A non-hovering mount will fall. Quickly. If engaging in high altitude flight, a reasonable duration stun - two turns, or a couple of failed saves - will result in you being removed from combat, and quite possibly in your rather messy terminal-velocity-finding death. Of course, this assumes you're using the updated flight rules also from the May 2010 errata (And you should, they're far superior). If you're using the old rules, hover is even better, as without it, you can't shift, and you have to move at least 2 squares every single turn to stay flying (This was removed in the may errata).