Ah, the eternal question of paladins killing evil things....
How I do it, IMC (and this is a slight reinterpretation, I think
Paladins are dedicated to the desruction of Evil.
Not to the destruction of things which are Evil.
It's a stubtle distinction, but an important one. If the paladin detects evil, it's his right as an icon of all that is ordered and holy to find out what makes the creature evil. You fight against the evil the creature has, not against the creature itself.
So, for instance:
1) A fiend. The creature is evil, and produces evil. There isn't a shred of goodness within him -- fighting evil effectively means physically battling the creature itself.
2) An undead. The creature is evil, but is unintelligent (for the most part), or is unwilling to change. Again, fighting evil effectively means fighting the creature itself.
3) A child who is a bully. The creature is evil, and undoubtedly produces evil, but there is the potential for goodness within him. If the paladin bodily fights the child, he isn't being true to his vows, he isn't fighting evil, merely the effects of evil. The paladin should, instead of killing the kid, find a way to turn the kid aroud, fight against the evil in his heart, and not his form.
4) A typically 'evil' humanoid. The creature is evil, and produces evil, but there may be the potential for goodness within him. This varies a lot by campaign, but normally orcs and the like can be swayed to goodness with only slightly more difficulty than a child. The paladin is obligated to attempt to sway the creature, but must preserve goodness above all -- if the creature isn't receptive, it is better to kill than to keep it alive.
All these assume the paladin has the legal right to kill all of these. Undead and fiends are 'monsters,' so there's not real question there. The child is arguably dishonorable, and an dult commoner only slightly less wrong. An evil humanoid may be within his rights, if it's a foriegner or a creature his nation is at war with.
I think I've covered most questionable situations with that look on it.
Fight the Evil itself. Not what happens to be evil.