Best method to incapaciate paladins: Insist that they be written up using only the core, official rules. Nothing from outside the Player's Handbook and Dungeon Master's Guide (Monster Manual for race if you insist).
After that, its a process of finding out if you like them chopped, bashed, skewered, fried, frozen...
The class blows like a Las Vegas hooker (variants and supplements might assist that, but I'm strongly inclined to doubt it.). Go for their Touch AC, their Reflex Save, their Will save (Ironically), straight up combat (There's an enhancement in the Book of Vile Darkness, forget the name, that halves the holy damage of a holy weapon, if my memory isn't playing tricks on me) as a fighter or something equally far superior at clobbering, and attack from a distance too.
Feints+Sneak attacks optional.
Basically, anything that you'd describe as a "strong character" that doesn't target Fortitude saves (their only real strong suit) or need to spread fear and disease.