I recalled a table in the DMG for higher leveled mounts (works like a druid getting better animal companions), but a google search was easier than going to the books.
Mount options. D&D 3.5 - Giant in the Playground Forums
"Okay. Found it. Page 204.
Level 6: Celestial Heavy Warhorse, Dire Wolf, Hippogriff, Large Monstrous Spider, Large Shark, Unicorn, Celestial Warpony, Dire Bat, Dire Badger, Dire Weasel, Giant Lizard
Level 7: Dire Boar, Dire Wolverine, Giant Eagle, Giant Owl, Pegasus, Rhinoceros, Sea Cat
Level 8: Dire Lion, Griffon"
Side note: Some creatures introduced in the "Races of" books as well as animals in Sandstorm, Stormwrack, and Frostburn were given animal companion equivalent levels and added to that list, I forget if they made them available as paladin mounts, too.