Lanefan
Victoria Rules
Easy. Mr. Paladin leaves the party, and his player and the DM sit down during the week over a beer and sort this out before the next session, while the main party goes without its Paladin for a while. In other words, the main session carries on as usual (with the Paladin's player running a different character), knowing that by next week the Paladin will either have his mount or not, and will be back in circulation once the rest of the party catches up in game-world time.But, you mention the paladin being unhappy about leaving his mount behind. Now, here's another textbook example of what I'm talking about. In earlier editions, you had to quest to get your mount. Great, fantastic flavour - the chosen of the gods goes out to secure his trusty steed.
Then came play at the table. What does the rest of the group do while Mr. Paladin goes out to get this mount?
This is a much better question. I've always kind of seen the mount's role as more a matter of looking imposing while riding into town, and for jousts and tournaments, than being involved in hard field work. And, if the Paladin ever gets involved in an army war, the mount again adds to the aura of imposingness. But it's quite true, horses and dungeons don't mix well; other than the horse providing food for the opposition.And, after Mr. Paladin gets his steed, what does he do with it? Most adventures don't allow for horseback riding. Unless you happen to be doing outdoor adventures in fairly clear terrain, horses are pretty much useless.

You're running aground on the 4e design paradigm of the PCs being special flowers, and the world and its rules revolving around the Party. Me, I'd just add a few lines of text in the call-for-warhorse write-up explaining how horses and dungeoneering don't often mix, and leave it alone.A game first approach would think, "ok, what do adventuring PARTIES (not individual PC's) do? What does a paladin need to help him do that and act within the party? Would a mount help? Is a mount a good idea for a fairly major ability for the class?"
If the answer is no, then the mount is simply not added and you go with something else.
Lanefan