Thanks for all the interest in my thread and the ideas you have all suggested.
replying in order:
Valadaar: He's old enough to know better, in his 30's! I like the fact that you mention the word "pride". To my mind the PC is definitely prideful, so that should play a part in his fall.
Drackler: I thought about this at work today, and I decided that I need to tell the players a little more about the campaign world to make things clearer for them, essentially what Wulfhere mentions. Being a teacher for some 14 years now, it comes naturally to reflect upon my own practice first. I can't blame my player for playing his character in a specific way based on his world view, if the world view is incomplete or misunderstood. So, I'm definitely going to let the party know more.
Pariah: I love the idea of the old hermit. I can just imagine him having to write everything on a slate, or mime! I think the word you are looking for is "Inquisition"? Perhaps after I add a little more to his world view, and lay down some clear do's and do nots, well, if he is still wanting to go down the fundamentalist route then we'll take it to its logical conclusion.
Wulfhere: He's already been called before the clergy, and whilst I got a "I'll change my character" response, well, it was just that...the player saying he will change his character, not the player roleplaying his character recanting his views. I was left with the impression my PC was not having fun.
What I'm really worried about is self-destructing the campaign (All my players knew each other before I turned up...apparently imploding campaigns have occurred in the past) and making it "not fun" for the other players.
My last thought on the matter is to agree with valadaar's comment about PC's who like to steal and murder, eventually they are going to be caught, placed on trial and hung. You know, if a PC was careless in combat (not unlucky, but does dumb things like run through 5 OA's unnecessarily) I wouldn't feel bad about saying "You're dead! Roll up a new character".
On the other hand, if after the watch capture a character who murders indiscriminantly, or is a heretic, and justice determines he is sentenced to death, I reckon I would feel very reluctant to say "They hang you. Roll up a new character." I'd be trying to find ways someone could rescue him etc... Sure, if the other players are willing to have their own characters made outlaws to rescue this PC then that's fine. But if not? Perhaps this is, to use an awful cliche, an occasion where the need of the many outweigh the needs of the few (or the one PC).
PS: Moonhunter, we were writing our posts at the same time, and you completed yours first. Thank's for all the great suggestions. I'll think I'll draw up a flow chart based on your ideas to give me a better overall idea of how to deal with my player. Whilst I like your suggestion that the other players have to make a choice too - to either support him and suffer the consequences of his action too, or denounce him, the only problem then is that I either run two smaller campaigns (not really an option), or declare one of the groups NPC's. I don't want to be taking characters off of players though, especially those who make their decision based on not wanting to end up on the end of a rope. Of course, if the denouncers turn the pro-fundamentalists over to the church authorities, that's another matter.
"Nothing brings a cleric/ paladin to heel faster than their deity turning off the power faucet." - I reckon mine would just &^%$@ about it, but I'm sure it would work with others.