Here is a scenario:

An evil woman pretends to be a helpless peasant girl. She convinces a group of 10 men that the PCs were discriminating her because she worships a particular deity other than their own and they robbed her of her coin purse and threatened to beat her if she speaks a word of it to anyone. Trying to be local good samaritans, they took it upon themselves to find the PCs, retrieve the purse, and teach the adventurers a lesson.

The men approach with weapons drawn just to make more of an intimidating presence. They confront the PCs, demand the purse back, and since the PCs respond with attitude and intimidation instead of trying to explain their mistake, one of the locals swings at a PC attempting to deal nonlethal damage. The PCs respond in full force and kill half of the men until the rest finally surrender.

This happens in a big city with laws just like any civilized city would have. The PCs were obviously more powerful than these men and one of the PCs is a Paladin. They knew these men made a mistake and were of no threat, but rather than doing what they could to explain their way out of a fight, or try to apprehend the men so that the authorities could sort things out, they killed them. The paladin can detect evil at will and never did. In fact, the paladin isn't even remorseful. As far as he's concerned, they started it and they got what they deserved.

That doesn't sound very lawful to me. I'd hate to penalize the Paladin, but this is pretty much his attitude towards every situation and it might be time to make him deal with the consequences if this is something that warrants it. He knows how to play a paladin (it's his favorite class to play), so a warning isn't going to remind him of anything he doesn't already know. What do you think?