Maybe just give the King a bigger "get out" tool?
Maybe he can single people out and hijack all their tax, block services, or incite rebellion in their region. All exile stuff would have to be through messages, but it would make the King position feel more...kingly. Open up options of "unjust treatment" or tactical usage for suspicious converts. My two cents.
