Or just make up a feat that allows the player as much as you want to give, of what he wants.
Mimic Practised Spellcaster from C.Arc, +4 effective levels re. Mount up to HD.
OR: Given how much better full caster levels are than the Mount, "Mount Bond", a feat that treats the pally as his character level for the purpose of the mount.
(Random Thought: this could be awesome for your player: rumour of old hero of order's excellent Mount skills, tiny side quest to find tome of hero, study tome - mytic experience! Vioila! The rest of the players want their own cool story line too!)
Rassilon.