In many cases, under pre-modern law, it was accepted that responsible (or merely wealthy) individuals could mete out on the spot justice to those who they saw committing crimes.
Yes, this is one of the (hidden?) assumptions I had when talking about Paladins in this thread. A Paladin can take strong action and then stand before the local Lord - if it even comes to that - and say, "I meted out the Justice of Tyr on an evildoer." He can do this because he is a respected figure. Unless the Lord is having some sort of political struggle with the Temple of Tyr he'd be generally pleased, and unless he wanted to have conflict with Tyr now he'd at least nod grudgingly and find the Paladin to be in the right. Maybe it's a bit of a Catch-22, but it would be a rare local Lord who would risk judging a Paladin to be "unlawful." ;-)
Anyway, this is obviously a digression about how to define Lawful and I'll throw this thought out -- being Lawful doesn't mean that you have to obey the laws of the city you are in. Otherwise, I'd have a hard time being Lawful Evil. ;-) Being Lawful means that you believe in some structure and organization; some set of rules and code of conduct. A Paladin gets this from his God; he doesn't need to get authority from mere mortals. (Though his God probably teaches that it is respectful to do so in order to avoid strife.)