Pariah and Exiles have their place but are very open to OOC grudge matches at times, while of course it can be reported if completely unfair such normally, resolved or not, leads to more of a grudge between people. Much of the arguments I have witnessed come down to how they should be worked towards getting them removed. So I propose the following.
Keep them both as settlement leaders that are able to place names onto either list, RP around the reason for each down to those in game and character actions. Their resource drains to maintain kept as they are too.
Implement an NPC on the boarders of each settlement, somewhere that can be reached for each by someone that is exiled without issue and have them issue quests similar to the radiant heart system. An inventory item offered that keeps track of the number of completed tasks, these tasks can be a number of things:
1) Writ works to show the character is working towards betterment of the settlement they are trying to seek redemption; these should offer no xp or gold. They should be one per day (or just under 19 hours or whatever the radiant ones are seems a nice fit).
2) Resource gathering quests, collecting resources and needed materials for the betterment of the settlement (in essence your character ensuring their own exile should not leave the settlement in a negative because of the cost of their own exile).
3) A fine, a coin costs of donations which could be set at the time of exile by the leadership when the exile is placed to fit the crimes, an example 10,000 needs to be paid for say a repeated theft spree, this can be paid in whatever increments the player seeking redemption wishes until the total of the fine is met which would go directly into the settlements account.
These should be spaced out to take maybe roughly 1 RL month at a minimum to complete 30 different ones. Allowing for both to still hold weight and not simply have someone grind to have it removed in a day or two of it being placed. Once the inventory item has reached a tick of 30 from completed tasks the same NPC will offer them a note of recommendation stating they have worked towards redemption and the pariah/exile should be lifted.
When the exile is placed by leadership (ensuring the rules are still followed in RP being needed before it is placed and the reason for it) there should be a few things they do when placing it, there could be tiers, Petty crime, Serious crime and Treason against the settlement. This should be picked to reflect the crime that has taken place and left to RP to determine, each could have a different time frame the exile will be held for at a minimum, as an example, petty crimes might need only 10 completed tasks and the fine amount be 10,000, a serious crime would need 30 and a fine of 100,000, treason and the higher end needing 90 and maybe 1,000,000. The numbers can be tweaked but I feel this would generate a huge amount of RP for the person to seek redemption while still keeping both Pariah and Exiles meaningful and in the players hands to implement.