The only way to make Paladins not suck is to get rid of the class and replace it with Crusader. Of course, you'd have to rework Steely Resolve to make it relevant and powerful relative to DDO. Abilities like Mettle would need to work for ALL spells. It'd take some doing, but the Crusader's martial powers could work very much like the monk's. The template is in place though, so I wouldn't think it'd be too hard.
It is known that Paladins are one of the weakest classes in PnP, so any "fixes" using PnP rules will just make them suck.
The only Paladin worth playing is the variant Paladin of Freedom, the Chaotic Good one, but only until 2nd or 3rd level (maybe 4th for Turn Undead and access to Divine feats). To fix Paladins and make them balanced with other melee, you're gonna have to think outside the box. To reiterate, don't use PnP rules to "improve" the Paladin. Almost all of PnP's rules of Paladins are horrible. If you do use any PnP rules, use the Divine feats already, like Divine Might, Divine Shield etc. Personally, I think the only way is to nuke the Paladin out of orbit...it's the only way to be sure.
Long live the Crusader (and the 4E Paladin, now THAT'S a Paladin).