I always figured that the key to a religions power was converting nobles, especially nobles in positions of power and by doing everything possible to ensure that those who gain positions of power are of the faith. Once that has happened, assuming you have managed to secure the characters loyalty, a role played "excommunication" can be truly painful. In this case I am referring to something along the lines of:
"All members of Religion X. This person has demonstrated themselves to be true heretics. It has been decided that they are to be excommunicated. From this point forward, none shall have any dealings with said individual. None shall support said individual in any way. None are to communicate with said individual in any way. None will allow this individual a platform from which they may influence others with their sinful ways. When this person has demonstrated their loyalty to the faith and has atoned for their wrong doings they will be welcomed back into the faith. Until that has happened any who defies this proclamation will be subject to disciplinary action."
If you have enough influential members this could cause some real issues for that person. If not, then you are kind of out of luck. In all I thin Indirik has it right though I think it could be cool if some features were added to increase the bite a little. Mostly passive things like hits to honor/prestige, negative reactions to peasants of the faith, the ability to ban from a religion, etc...