One possible solution would to make a way for priests to get to hire body guards that are specialized against thievery and cost 50 gold a week. It will be spendy (50*52=2600 gold a year just to defend from pirates) though maybe it should only be 25 gold per week.