Ridley's Cohort:
In the abstract, I agree with you.
In this particular case, though, it seems that there was plenty of opportunity for the paladin to check with church authorities, and that, in his church (hyper-lawful), it would be expected that the paladin would check-in unless circumstances would prevent him from doing so.
I infer that there was plenty of time for him to check with church authorities from the fact that he rather deliberately planned the retribution for the bandits. Also, IIRC, didn't he start in a civilized land near church authorities, teleport or something over to the bad guys, kill them, and then teleport back? It's not like he was deep in enemy territory or something.
As the Bandit Kingdom doesn't have a court of law to appeal to, the Paladin decided to go there...
And, when it was all said and done, he air walked home (alas, minus the tent and donkeys)
It just looks to me like he spent some time planning, and that he started and ended in his own home territory.
The way I see it, he was personally quite upset at what was done, and he decided, on his own, to act on behalf of the church, with church authority, to conduct a punitive raid on the Bandit Kingdom to hunt down and kill those who killed his retainers. Very un-paladin-like behavior. He really should have gotten specific authority for his acts before committing them. He had plenty if opportunity to do so (well, I think so, I really don't know that for sure).
Repercussions should be forthcoming. This should create a great role-playing opportunity.