the issue for me is not the kicking, it's kicking with complete impunity.
what if, as a temp solution, you can kick. but if it's a priest of long standing/high skill, then every region with your followers will kick up a fuss - magnitude depends on follower lvl, priest's standing, etc...
a bit like sacking a shrine/temple..
also as a temp thing, a separate "silence" function could also be added to make preaching/influencing more ineffective
spamming is an ooc thing. sic the titans on them.