I wouldn't say Paladins are that self-sufficient. They can't really AVOID trouble at all; no invisibility, no flight, no way to detect traps. They don't have enough Feats to get all the good combat abilities (although the semi-brokenness of Divine Might et al makes up for that somewhat).
Campaigns with multiple Paladins CAN work; just look at Piratecat's.
The Achilles Heel of the Paladin, though, is the alignment. You MUST be Lawful Good, and you have a very strict code of conduct. This also extends to your party; if the rest of the group is Chaotic Neutral, you just wouldn't stay with them. If they go off stealing, a normal LG person might be able to live with it, but a Paladin wouldn't.
This especially works well in a world where morality is fuzzy. If Orcs are pure evil, then sure it's okay to slaughter them all, but if Orcs are just another race that happens to be at odds with the Humans, then it's not something a Paladin could do.
This causes Paladins (in my experience) to have a problem with political/social adventures. They'd fight against Robin Hood simply because he's a thief and because the King is the Law. The fact that he taxed too much and gave too few freedoms don't make him "Evil". It's nothing a feudal society doesn't expect. If no one is inherently Evil, his class abilities become practically useless.
(This only works if you have a VERY smart DM who can control the situations the players are in finely enough to have them siding with the Sheriff instead of Robin Hood. Control what decisions the Paladin is exposed to, and his code of conduct will force him to act the way you want him to.)
As to how to keep him from playing a Paladin? Here are the options I'd give, in order:
1> Tell the guy no, you're tired of him playing the same character over and over, and he either takes something different or finds a new group to join. People are allowed to have favorite classes.
2> Don't let him take any splatbook abilities. The pure-PHB Paladin is FAR less powerful. Remember, splatbooks are entirely DM's discretion.
3> Have the rest of the group be predominantly Chaotic-types. He wouldn't be able to rationalize, in-character, staying with a group like that, especially if you don't give them some sort of "greater good" mission yet.
4> Have the rest of the group be fighter-types or healers, and tell him the group needs a spellcaster. It's his turn.
5> Make it so that there are no Paladins in the world. Maybe there's no LG deity for them to follow. Maybe there's been a purge, and all of the holy orders were destroyed. Maybe it's only a local thing, where the campaign starts in a very chaotic city.
6> Nerf Paladins; after all, clearly if he plays ONLY Paladins they must be too powerful. Maybe they can't use piercing weapons (there go ranged attacks and lances). Maybe they don't get healing spells. Maybe they take a vow of poverty, and have to give away all loot to orphanages and such.
