Better yet, allow a priest to hire burly commoners to accompany him. They could not only help protect him from highwaymen, but from unruly mobs and soldiers attempting to capture him as well. Of course, merely being mercenary thugs their loyalty should never extend too far, and so they should be unable/unwilling to ever fight a pitched battle. I see this working best as a substitute unit that's always neutral.
Or another idea - give priests a travel option similar to those that adventurers have (eg hire ferry) except call it "hire escort" and have it drastically reduce the odds of being robbed when used.
Both options could be rather pricey, to discourage overuse.
