I really think that a change in player approach is the only really answer to the religion issue. As I understand it most medieval people places religion at the fore in their lives. In many cases loyalty to the church was as great a priority as ones loyalty to family and realm. More so in some cases. The churches views were your views. It was better to die in obedience to the church that to live in defiance of it. Your brother defies the church you halt all associations with that guy and might even hunt him down to clear the family name. Your country goes against the word of the faith you find yourself between a rock and a hard place. Unless character are played like this, religion will never be what it, in my opinion, should be.
That being said I think it may be possible to encourage players to play characters as being more dedicated to their faith with mechanical incentives. I am not 100% sure what these mechanics should look like. The only religion that even comes close to commanding this kind of loyalty is Sanguis Astroism and I am not sure if it's accomplishments can be modeled or even fully understood.
