IanB said:
Presumably in your example, the NPC Kord-worshipper in question isn't a physical manifestation of everything that is evil in the universe, though.

It is also somewhat unlikely to me that the legal framework the paladin subscribes to offers any legal rights to extraplanar hellspawn.
So much of this discussion is tied up just in how you frame the paladin's actions.
One camp seems to think this is what happened:
- Paladin makes agreement with invisible creature, planning from the start to take him out once said creature is no longer important.
But it could just as easily be:
- Paladin says nothing when his group makes a deal with an invisible creature, perhaps having misgivings but keeping them quiet in order to avoid a scene with his group, and as they progress through the search gets more and more suspicious - in the end, when their ally is revealed to be an evil imp, he realizes his mistake in not piping up earlier and attempts to rectify it (and salvage his paladinhood, which could be endangered otherwise) by destroying an evil abomination that opposes everything he stands for.
They're the same thing in terms of actual character actions taken in game, but very different in character/player motivation. We don't *know* what the player was thinking at the time.
EDIT: Also, due to the fact that MAD is a harsh mistress and the realities of the point-buy system, there's a good chance that the paladin has only an 8 intelligence. Does that change anything about the situation? It might easily explain why he didn't think to detect evil when it was just an invisible helper, for example.
Let's try another scenario. I'm interested to see what the 'Kill all fiends' people say for this one:
The end times are near. Orcus has nearly completed a ritual that will infuse the soul of the entire world with negative energy, which will turn all the living into undead, allowing him to rise from the formerly pure Lifepool, now the Deathpool, and rule over his new world of the dead. To finish the ritual, Orcus needed to place three magical foci in three different planar locations. The only way to stop him now is to break into one of them and destroy the focus before Orcus notices the intrusion and sends his strongest minions to stop the heroes, or comes himself!
Unfortunately, finding the foci, which are each on a special demiplane with a special key pass phrase, is a difficult task. Even a Miracle spell can reveal only this: Two of the foci's pass phrases are known only to Orcus himself, as he has killed the ones who created these places and eaten their souls. However, he made a crucial flaw with the third--he had thought the creator of the demiplane, the angel Anyiel, was destroyed, but actually, she had Fallen, and that is why his magics had told him 'The Angel Anyiel is no more'.
Anyiel is now an Erinyes. The group contacts her and finds that she has already heard of their exploits. Though she fell from grace, Anyiel is still a creature of order, and indeed, she has a strong attraction to paragons of Law and Good that remind her of what she has lost. Furthermore, she thinks the group's paladin, Sir Pelinor, is quite handsome. So she makes the following request: "I want to have a nice candlelight dinner in Sigil with Sir Pelinor in Sigil. If you all promise me that and also promise not to harm or hinder me in any way, I shall be glad to provide you with the pass phrase you seek. After all, it is not as if I want to see Orcus's chaos envelop your world."
So what does Sir Pelinor do, people on the 'Kill all fiends!' side? I'll present some options--or you can pick your own.
A) Sir Pelinor has a nice dinner with Anyiel. Anyiel tells him the pass phrase. He returns to his comrades and they use the pass phrase to stop Orcus's plan. Anyiel returns to Baator and tells all her Erinyes sisters about her hot date with Sir Pelinor.
B) Sir Pelinor refuses because this requires contact with an evil outsider. Orcus turns everyone in the world into undead and rules the world.
C) Sir Pelinor agrees, but when they meet at the restaurant, he decapitates Anyiel. Take that, bitch! On the downside, Orcus becomes supreme ruler.
D) Sir Pelinor agrees to the terms and has dinner with Anyiel. The moment she whispers him the pass phrase he sneers 'Foul creature. I can't believe I had to pretend to have a civil dinner with you,' and decapitates Anyiel. Then they stop Orcus.
E) Sir Pelinor says nothing as his party agrees for him and makes the arrangements. He goes to the appointed restaurant in Sigil because he overheard the party's agreement. Then he sits at the same table with Anyiel--not because he's having dinner with her or anything, oh no. In fact, he's not really associating with her, but that seat happened to be open. Once she gives him the pass phrase (assuming she does so despite his rudeness), he grins and pulls out his sword.
"But you promised..." she protests in horror, a helpless and betrayed look in her eyes.
"Stupid hellspawned bitch, I never agreed to your terms. Only the rest of my group did. Now rot in the Hells where you belong!" and he decapitates her. Then he and his comrades stop Orcus.