Here's the intended situation:
There's a religion based on the premise that the priests are protecting the general public from evil magic. Use of magic is taboo. What they call magic is actually leftover technological artifacts — mostly weapons — from an ancient, very advanced period. Now magic is extremely rare and the majority of people have never experienced it in their lifetimes. This has lead to the majority of people no longer believing that magic actually exists.
Now the problem is, why would people stop believing (but without actually leaving the religion entirely)? In our world, it's usually science which causes people to lose belief in religious dogmas (and while some lose faith altogether, others simply adapt their belief system to fit what they know from science). But in that society, there is no science whatsoever; they are essentially back to medieval thinking, and in medieval times, lack of evidence certainly didn't make people disbelieve.
So my question is: Is there a way to make this setting believable?
Edit: I do not want the religion to be replaced by another one. I want the religion to be dominant, and in particular the values of the society to be based on that religion. I just want the majority of followers no longer to believe in the basic claim that there's magic and that the priests protect them from that magic.
Also, by “science” I basically mean the scientific method (and in particular, the way of thinking that comes with it).