I see alignment as much simpler than Hypersmurf is trying to make it. Hypersmurf is trying to turn this into a Rules Forum debate. (No offense Hypersmurf, but this *is* how you argue in the Rules Forum.)
The Universal Powers That Be (UPTB), be they the gods, the tangible and objective powers of Good, Evil, Law, and Chaos, the DM directly, or whatever, are what decide who is evil and who is not.
A paladin fights and destroys evil. For this, the UPTB give him detect evil and smite evil. If that evil person is in the process of redeeming himself, and the paladin uses detect evil on him, the result will be based on what the UPTB decide. If the UPTB think that person is no longer evil because of a change of heart, then he will not show as evil. If the UPTB think that person is still evil because he has not yet done anything not-evil or good, then he will show as evil. Whatever the result of the detection, the result will be the direct decision of the UPTB (read: the DM).
I don't think the UPTB should be in the business of trying to trick paladins with his UPTB-granted powers. Mortals may be trying to trick the paladin (with the rarely used, but often threatened misdirection spell), but the UPTB have set up the rules, and they (read: the DM) should stick by them.
A DM saying, "You have the ability to detect and smite evil, but not all evil you detect will be really evil and deserving of your smite," is just being a jerk to the paladin's Player.
If detect evil is so inaccurate, why bother with it at all? If the paladin can't trust the UPTB in a campaign, then why play a paladin? Play a LG fighter -- at least that way the Player won't be tricked into thinking someone is evil before actually witnessing an evil act. And after witnessing an evil act that he could have stopped by being proactive against the evil, a fighter can't be stripped of his powers by the tricksy and unpedictable UPTB (read: the DM).
Quasqueton