Why not simply have a button that every single Elder of the religion must press in order for the Priest to be kicked out?
It allows a truly troublesome priest to be kicked out, but also requires a significant consensus to do so. It allows the possibility for arguments and conflict, because if the troublesome priest has just one ally on the Elders, then he can't be kicked out.
Therefore, it would get rid of 100% immunity but also not make it an easy or wishy-washy matter to simply boot a priest.
This is the request I would press forward with, and dispense with any further hypothetical mechanical penalties for kicking out a priest until you're ready to implement full schisms. It sets a somewhat high bar for actually kicking out a priest, and leaves room for ongoing conflict in the event that the Elders are divided. It satisfies my concerns, and hopefully yours Tom.
And, it
appears to be fairly simple (says the non-programmer).
