I don't really care about other people's arguements or even the ofiicial rules on this one, the way I've explained to my players is that every mortal* creature has the possibility of both free choice and redemption and if possible should be saved rather then being killed. Paladins should not massacre evil, except when they have proof that they have either committed evil and a crime (that is punishable by death) or are in the act of doing evil.
This has never really gotten in the way of the game because 99% of the time, paladins only encounter evil creatures (big, bad, smelly, stinks of evil kind) in a combat situation. Otherwise, a paladin would be breaking the law by slaughtering someone evil that hasn't comitted a crime that can be proven. Of course, the paladin can kill someone but normally they can only get away with it once or twice before a LN officer would arrest them.
A paladin may not get arrested for slaughtering the innocents of orcs that are hated in a given area, but they certainly wouldn't be liked, respected, and probably seen as a fanatic in most cosmopolitian locations.
*Mortal creatures are anything that has a finite life span, two parents and needs to eat. Thus undead, magical beasts, outsiders & aberrations generally fit outside these parameters and are not believed to be subject to free will. They are what they are, so if something smells of evil, the paladin can go smite-happy on the thing.