I think this quote sums up my main problem with the approach that's been mentioned by many in this thread:
In my eyes, a paladin is not common.
Having a paladin as commonplace not only strains my believability from a human psychology point of view (e.g. there are DAMN few people that are willing to lay their lives down for the common Good), but it also completely skews the balance of normal vs spectacular beings (i.e. if paladins are common, than so are anti-paladins, therefore the extremes of personality are rendered too familiar).
It is made quite plain in the conventions of the class that paladins are the rarest of breeds.
If they were as common as other classes, than everything written about them is suspect. I know that us roleplayers may choose them just as often as, say, a Barbarian, but that doesn't change the fact that within the genre, they should be the rarest.
Remember, in D&D we are playing (what should be) a very rare individual : an adventurer. To make them (or trolls for that matter) a common sight in everyday life is to skew the dynamics of the world to the breaking point (for me).
It's similar to vampires in the World of Darkness : IIRC, the ratio there is 1 vampire for every 10,000 common persons.
I wish D&D had this kind of guideline, so that people don't (quite reasonably) begin to assume that adventurers are the norm.