In a previous campaign, we also had a paladin lose his status in a similar incident, although his was more justifiable, and more of a chaotic action than an evil one (one for which he was assigned a quest to regain his powers). This earlier Paladin had witnessed another PC burn down a barge that the characters were guarding, and had then witnessed the PC murder the bargemen with flame arrows when they tried to beat him and tie him up. Another PC restrained the errant sorcerer, and our Paladin decided to pass judgement immediately, having witnessed the sorcerers action. He beheaded the restrained, helpless sorcerer. As the killing, in this case, was readily justifiable (he had witnessed the sorcerer using undue force to slay a few commoners angry that their livelyhood had just been taken from them), it was not what I would call an evil action, but he had certainly overstepped his bounds- he announced, before performing the execution, that it was "The will of his god"- whereas I had explained to him earlier that the murder of a commoner, under the code of law of the kingdom (written by a patriarch of the paladin's own church, no less), was only punishable by ten years of imprisonment in a labor camp per person killed. Only murder or rape of an aristocrat (noble, knight, clergy, or guildmage) warranted the "death penalty".
So- was I warranted in stripping the paladin of his powers (all three of the other players agreed with me)... or was his action justified? Or should it have been considered a chaotic action rather than an evil action- punishable by temporary loss of powers, but not permanent?