Personally, I'm way too forgetful to keep past titles except in very few circumstances. Usually, if I remember dealing with someone when they were a higher rank, I still afford them the respect, but not the title itself. It also depends on the kind of title it was; if someone can acquire it easily or is easily removed, I'm less likely to grant them the respect after they've lost it. (For example, someone who is only a Marshal and loses that title is still essentially a Knight. I am unlikely to know the reason why he lost the title, but if he has no others, it's not likely a nice reason.
My rule is simple: If in doubt, check the Message page and pick the most relevant.
As for religion, my characters generally treat holy men with respect because they've dedicated their lives to their gods... but I completely ignore their authority if they're not of my faith. My realm? My laws. My region? My religion. I eagerly await the day a high-ranking member of a religion steps into Coria trying to convince us to do something Ravendon doesn't agree with.
I will note, however, that I always get confused with personal messages and befriended characters. Generally, I'll keep up titles for respect unless I'm really trying to appeal to their nature or emotion. Yet somehow, saying "Merlin" without a title feels weird. I think it's an OOC concept of the "real" legend.
