I feel that playing a good alignment is vastly more difficult than playing either a neutral or evil alignment. I don't necessarily agree with you, Hammer although I see where you are coming from very clearly. I've played what I consider successful evil characters and somewhat unsuccessful evil characters. Generally speaking, so long as an evil character is intelligent and doesn't flaunt the fact that they are evil then they can beat any good aligned person 9 times out of 10.
Here is how I view alignment, and why I think being good aligned is the most difficult.
Good is based around morality. You hold certain key values that make up the core of your being. They exemplify the virtues of mercy, forgiveness, hopefulness, redemption and compassion. They strive to help others, offer charity and do so at great personal expense. This is what it means to be good aligned.
Contrast this with evil who is literally the reverse of all of those things and based around immorality. They embrace the concepts of vengefulness, hopelessness (often through oppression), corruption, hate and fear. They strive primarily for themselves, care little for others and are only likely to do something at a great personal expense if it furthers their own goals or aims.
Neutral aligned people fall somewhere between the two extremes, but that is what good and evil are fundamentally - extremes. They are more closely linked to amorality, they may lean either toward good or evil, but lack either the conviction of a good aligned individual or the sheer depravity of an evil aligned individual.
It is for these reasons that I have trouble accepting so many Paladin's in Sanctuary, and why I do think becoming a Paladin should require an application. I see the class as the embodiment of all of those good ideals and much more. They are held to such a strict code of conduct, it only makes sense that their numbers - especially here in the Underdark - would be highly limited.
A Paladin has virtually no hope of surviving any extended period of time in slavery. By the time he makes it to the nearest evil settlement he's likely to find himself strapped to an altar and sacrificed to an evil deity. Even Clerics are in danger of this. Read Oro's post on slavery in the General Discussion forum for reasons why.
So even getting to Sanctuary through the typical means (escaped slave) is difficult for a Paladin. So that means the Paladin is likely to either arrive in Sanctuary through unorthodox means or become a Paladin while in Sanctuary, after character creation. (Many already do this as evidenced by the Fighter 4 / Paladin X multiclass.)
Keeping that in mind, shouldn't becoming a Paladin be more than simply selecting the class on level-up? Shouldn't it be some type of mystical experience, even if you are already playing a deeply spiritual and religious character? You are literally becoming a Chosen Warrior for a god, it isn't something that you simply wake up one morning and simply become. It is generally speaking a process.
So it is for those reasons, and others that I made my suggestion in this thread. I do not feel that the problem with Paladin's is their strength. Anyone who has proper time to prepare can kill a Paladin. (Preparing also meaning bringing along some friends, not just buffing up for a fight.) I don't believe Paladin's should be easy to kill - they are blessed by a deity. Anyone is hard to kill if they are prepared and you're not - in fact on EfU this is almost instant death, and the best advice that can be given when faced with an enemy who has come ready for battle is to run. Run and return to fight the battle on your own terms.
I think this is primarily the gist of the suggestion: Paladins are over powered and require a weakness. The above is my counter suggestion.