I put the men on surrounding lands, and my sergeant (Katriona) on guarding the roads, and they had both hit 'Low' when some neighbouring town commented that bandit raids were getting worse, and he was asking for help.
Given I was a Paladin this time around, and a good guy, I dispatched half o my garrison there to help him out. He was QUITE grateful (and Kana thought I was insane). But I figure if I can inflict hard justice against the bandits, there will be more deterrence. And a dead bandit, is a bandit that will rob no more. I recently put merchant tithing to low (from none), and peasant tithing is still low as well. My men are back, but I've now "exhausted" them, which it seems is just a catch that now says "Go play the story and come back later."