Just some things I noticed on the Lists of Stuff:
stacks for paladin special mount
Halfling Outrider, ecl 6, Complete Warrior
Wild Plains Outrider, ecl 7, Complete Adventurer
Cavalier, ecl 9, Complete Warrior
Knight of the Iron Glacier, ecl 7, Frostburn - War Megalocerous only
Ashworm Dragoon, ecl 6, Sandstorm - Ashworm only, see sidebar on p.67, unclear wording on how levels stack/overlap with Paladin
Aglarondan Griffonrider, ecl 8, Forgotten Realms: Unapproachable East
Triadic Knight, ecl 6, Champions of Valor
Vandalis Beastkeeper, ecl 5, Eberron: Dragonmarked
Bone Knight, ecl 6, Eberron: Five Nations
special mention
Wizard 5 (High One Warrior-Wizard substitution level), Champions of Valor web enhancement, combines mount and familiar
Devoted Tracker, feat, Complete Adventurer - stack benefits of animal companion and mount
Swift Call, feat, Complete Champion, call mount as a swift action
Drow Judicator 5, ecl 12, FR: Underdark, call a spider servant
Celestial Mount, feat, Book of Exalted Deeds, mount gains celestial template
Sanctified One (Elhonna) 1 or 3 or 5/5, ecl 6, Complete Champion, "nature's mount" see text
I don't know much about paladins, so I can't do a lot more to help than that.
Edit: IIRC, Races of the Dragon has rules for using a Dragon as a special mount.