The 'normal' levels of most NPCs rarely reaches as high as fifth level. Personally, I tend to limit NPCs to beneath tenth level, and only the exceptional ones reach above fifth.
If you are lower than fifth level, a war horse is a significant, potent, lasting mount.
Once you get to levels 5+, it is a good idea to start looking for other types of mounts. Hippogriffs, Griffons, Unicorns, Nightmares, Manticores, and Gorgons all come to mind . . . . And this is not even taking into account more exotic mounts at (even) higher levels, such as dragons and dinosaurs - or even just adding a template or two to a more "normal" mount. Or just using a Construct in the shape of a 'normal' mount - such as a stone golem horse, perhaps?
Isn't there a type of dragon / horse creature in MM I ? What about the Dragonne? At 9HD it is more a mount for levels 12-16, perhaps, but it offers an idea of what might be more 'typical' at higher levels. What about Lamassu and Sphinxes?
Really, if you keep increasing in level, you would seek to have a mount that could both last through combat and offer new and useful options during combat. If you are epic enough, even a tarrasque could become a worthy- of- consideration mount.