Just as a thought experiment, imagine the problems that would arise and the effort required to address them if you wanted to make a different change: adding Centaur as a playable PC race.
So right off, you've got sizing and animation issues. You can't restrict the PC from going into a subset of dungeons, so you have to figure out some way to make it work with all existing dungeons without looking really goofy. That includes:
- Climbing ladders
- Scrambling up narrow ledges
- Swimming, both on the surface and underwater
- Corridors with low ceilings
- Jumping on things with small footprints -- floor buttons, Shroud lights, traps, those pillars in Rainbow in the Dark...
Now it's okay to say that most quests would work fine, and only some would have problems. But the DDO code doesn't have a flag in it right now for "okay for big 4-legged beasties". The closest you've got is perhaps "quest vs. explorer zone". So everything has to be reexamined, and some things potentially altered. You can't have a flag that says "horse not able to be ridden here" unless you go through and exhaustively check and test everything.
Because it's borderline okay to have goofy Artificer dog animations and teleporting hirelings in order to get around this stuff, but it's not going to be okay when it's your PC. To say nothing of the suspension of disbelief. It's bad enough that the guests in Partycrashers don't turn their heads when two bears, a mindflayer, a hezrou and a halfling walk into a bar like it's some kind of bad joke... Now they have to be polite and ignore the man riding on an 1800 pound warhorse too? Remember, the DDO game doesn't know if you're "inside" or "outside" -- the terms don't have any meaning, unless some dev takes the time to go through and flag each and every area.
I'd submit that the "paladin on a horse" is going to run into all of these same things, and so would require a really substantial amount of effort to get right. This doesn't even address game mechanics -- extra damage, or how it affects your reflex save, or whatever. This is just the baseline "don't make it look stupid" check.
Even if you restrict things to Explorer zones, you still have to deal with the goofiness. Do you let the paladin ride his mount up into the Gnoll village in Meredia? If not, how do you code for that? I'm sure the engine doesn't distinguish between "place you could ride a horse" and "place that you can't". It's okay to have beasties that are bigger than human size, because the developer places those individually where they make sense. Not so much for the Lone Ranger riding Silver into every crypt in the Orchard.
Basically, I think mounts (like flying) are something that have to be designed in from the start. You can't retrofit them onto an existing world that has already made lots of assumptions about the size of PCs and their basic animations without more headache than is justified by the benefits.
Would it be cool? Sure. Do paladins need a boost in power? Definitely. Is there a way to do it cost-effectively? Not that I see.