re-what?
There was very little of that in medieval europe, including the times before christianity held sway. People were killed for having a different religion. Some like the jews were tolerated, mostly because they could conveniently be persecuted whenever you needed a scapegoat and partially because their religion was at least a variant (in BM terms).
I can not imagine the christian baron of an european barony to order the construction of, say, a temple to Wotan/Odin.
The fact remains that religious tolerance
does exist in-game. Stating that it didn't exist in medieval times doesn't change that.