Anything else to do with MoM IME
Paladins are really awesome, but it does take quite a bit to get to the level where u can make them. There naturally are good counter-paladin units as stated above, but the best would be Longbowmen from the High Elf race. Ive had Adamantine Longbowmen with lionheart and spelllock on em and they would sack paladins before they even got close =/ Sky Drakes too for that matter! Longbowmen are godly! (if not longbowmen then Rangers from Nomad race are pretty good too, or Halfling Slingers). Adamantine and Mithril infused units really make a big difference though.
I think lionhearted adamantine longbowmen had about 14 ranged attack power and 11 melee attack =/ Btw. any hero with 25ish + ranged magic attack power can hurt the paladins too, itl smash through their magic immunity but do reduced damage most of the time, and sometimes none, at 30+ ranged magic attack itl start doing more and more to them.