I don't think nomadic type of life would suit pilgrims. Witches on the other hand...
How about inverting PvP mechanic for witches as well? Pilgrims, when they commit crimes, are locked to their homestead and have to erect defenses around it. Witches on the other hand could be forced to migrate and hide in the wilderness to escape revenge.