It's definitely not the answer you're seeking, but in my campaign, since I hate Pokémounts, I told the paladin he could have a celestial warhorse in exchange for being able to summon it back and forth.
You can of course use the 3.0 permanent special mount, or as an alternative you can give the paladin a celestial servant similar to the blackguard's fiendish servant.
There was something somewhere and I do think it was the BoED.
I have seen house rules where the paladin summons a spirit guide/guarding angel that he could talk with. The player and DM worked together to come up with rules dealing with it, things like type of answers to get, exactly how much help could be provided, and where the spirit could go. I was impressed with it.