I think the main problem with the so-called "MAD" classes is that people ignored the advice in the PHB.
PHB p90
Paladins start with two common builds: the avenging paladin and the protecting
paladin.
The problem is that many players seem to think that there is a third build. What I like to call the "But why can't I do everything" Paladin. Or Cleric. Or Ranger. Or Warlock. While some classes like the Fighter and the Wizard can go through life concentrating on one Attack stat, other classes have more difficulty doing so. In those cases, it's best to just pick one stat and stick with it.
Yes, there is no Strength power at level 9...I know. However, I'm betting that will be fixed in Divine Power. It sucks that you have to wait awhile, but I'm sure that most DM's would give you some leeway to change one of the Charisma powers to a Strength one. Or go MC Fighter and take a 9th level Fighter Daily. Victorious Surge would be a great choice, and it's even a free heal!
Plus, if you actually read the Avenging Paladin build write up it says the following...
PHB p90
Choose
Strength as your highest ability score, since your most
damaging attacks are based on Strength. Charisma
should be your second-best ability score, and Wisdom
your third. Consider wielding a big two-handed
weapon such as a greatsword or greataxe, and choose
powers that deliver the highest amount of damage.
In our party we have two Clerics, a Fighter and a Paladin. Our Paladin is a Greataxe wielding Dragonborn that followed this build write up practically to the letter. Does he heal a lot? No. He only has a 12 WIS. I think that's a little
too low, and that an 18/16/14 STR/CHA/WIS might've been better...but it's his choice (You could go 18/14/14 with a Human easily, and still have 12 left over for INT or CON). The point though is that he's able to do okay DC damage, is really good with the STR powers and has some limited healing capacity that's not needed as much because we other primary healers. He doesn't
try to do everything at once, and because of that he's very effective.
As the primary Defender it's my job to do the marking are really try to slow down the enemy. I wear Scale and use a Heavy Shield, so I'm actually a point ahead of him...which is kind of good because it means he's a
slightly more attractive target than I am. He does a little bit more damage than I do because he uses a two-hander, but I can mark and lock down more targets. So he does a great job of being the harder hitter, but less armored, Defender and attracts a lot of attention. Between the two of us, we make a good team...and that's what most Pally's are really good at. They're good at being the
secondary Defender that's paired with another Defender. IMO I think that Fighters are probably the best single Defenders (generally speaking, depends on party makeup) but that any combination of two Defenders will be effective because they play to different strengths. The Pally is great because he can forgo a shield and pick up a two-hander and be right there in terms of AC with the Guardian Fighter
One last thing... While the book in both builds recommends WIS as the tertiary stat, I don't think this is always the case. I think you can make a very good STR/WIS or CHA/WIS Pally and be fine. Alternatively you can go STR/CHA/WIS as long as you keep your priorities straight and don't try to do EVERYTHING at once. Because 4e is more cooperative and more about the party working together you don't need to have these classes that can do everything. What you need is a group of 4+ specialists in diverse roles tying everything together to work as a cohesive unit. It's the whole idea of wanting to be a generalist that ruins a lot of builds (see, for example, our party Ranger that wants to be able to do both Ranged and Melee combat...and therefore can't hit at either of them). Specialize your character, pick one or two things you want to do, and then stick with that.