Tricky, but I think we can nail it. What you're looking for is the Big Familiar feat from the Netbook of Feats; you'd need to take it twice for a Large creature(evidently the writers of the Netbook have some experience with us players abusing the system). Now, the problem is that the description specifies the familiar-to-be must have the Animal or Vermin type before commencing the ritual, but the Paladin's entry does not say your mount could not have become a Magical Beast before you got it. As far as I know, the SRD does not state where these Mounts come from either. Since they aren't Outsiders, you can safely assume they are but ascended mortal steeds, regardless of where they come from; it's well known the Outer Planes, Celestia incuded, houses mortal beings along with petitioners and Archons.
So you need to get the feat first, buy a horse, bind it to you for the price of two feats, then specify it as your Special Mount. How's this? Worth it?