I voted "Uplifting the downtrodden."
The paladin's duty is to protect civilization. Killing unredeemably evil creatures is well and good, but not necessarily the most useful task.
Let's take a lich for example. They are always evil (please, don't confuse my example with baelnorns and archlichs). Let's also take a despot. He's not exactly evil, rather lawful neutral without good tendancies. He's more interested in the strength of his armies and the content of his coffers than with the well-being of the citizens under his charge. He has harsh justice and heavy taxes.
If the lich is raising an army of undead to-take-over-the-world-bwahahahah, as they frequently do; then defeating it is a paladin's duty, and he will warn the despot of the danger and ask for a battalion to fend off the zombies while he will go after the lich.
If the lich is merely reading dusty tomes alone in its faraway tower, then it may be more important to pursue another goal, like lobbying the despot into more social justice, or even helping political opposition. While still keeping an eye on the lich, were it to become menacing.