Alternatively, I recall something being bandied about about actually having a pantheon, and then people would have differently religions interpreting the will of the gods that absolutely existed, or supporting one instead of others and the like. I didn't like it before, but with the vast increase in the fantasy quotient after the last few Invasions, it might be appropriate.
I don't see how a pantheon relates to the fantasy quotient... It's not like the middle ages wouldn't have come about with a polytheistic religion rather than a monotheistic one...