Well, historically, magic and spell-casting doesn't really mesh with faith in the Christian God. According to the Bible it's just witch-craft - the Devil's domain. It's one of many reasons why I have trouble to think of D&D as a good basis for a medieval setting that is supposed to be mostly historically accurate.
In Ars Magica that's one of the main reasons why the Church is wary of Magi. Some rare beings have 'True Faith' which allows them to pray for Miracles, which is completely different from using magic. First, there's no guarantee anything will happen, and second the actual effect of the Miracles isn't under the control of the supplicant.
Pagan gods are 'just' considered powerful faerie beings in this system, btw. Which makes sense since faeries draw their power from (re-)creating tales and legends told by humanity. Devil worshippers are granted powers by Demons in exchange for their souls. These 'gifts' are invariably tainted and granted in the hope of leading to sinful behavior and causing others to commit sins. In fact, the most powerful abilities of Demons in Ars Magica are their 'Psychomachia' which allow them to cause humans to experience sinful emotions. (It's important to note that since the victims of Psychomachia aren't acting out of their own free will, this doesn't actually endanger their souls directly. The idea is to make them 'get used' to sinful behavior and make them commit sins consciously at some future point.)
I get that you don't care about historical accuracy as much and mostly want to benefit from a well-defined setting and still use D&D mostly unchanged, but it's tricky to explain why the changes you are making to the setting's reality don't completely change its nature. Even if you don't care about using a different RPG system, which I completely understand, it can be beneficial to read about different ideas on how to solve these conflicts in ways that make sense.
I was at an RPG and Comic book store called "Gamers Gambit" yesterday, and I saw Ars Magica in the shelf, I picked it up and looked though it, a lot of interesting stuff in there, but I wasn't ready to make an investment in it yet. I would like to see what would happen if I adapted a historical setting to Dungeons & Dragons, either 3.5 edition or 5th edition, I haven't decided yet, I am more familiar with 3.5 but I have both. I am working on a map, a more clearer image than the one I showed you of Europe. Basically I'm replacing every hex at twice the resolution and renumbering and relabeling each hex. The numbers are somewhat indistinct when you look at the hexes close. I am almost finished with hex replacement and will post that map when I'm done, this will be a map without labels, just the terrain hexes, and I will overlay the labels and city locations and so forth. Once that map is complete, I intend to make encounter tables for each hex type.
For the record, I always thought medieval people were a little nuts about religion for instance when I google "Medieval Paintings" I get this:
These are the first four images I got, medieval people lived and breathed religion, when ever a medieval artist picked up a paint brush and wanted to paint something, it usually was of a subject having something to do with religion, which is not usually the subject of what you'd find in a fantasy novel. Most fantasies graft a pagan religion, with a bunch of made up gods I never heard of, with a pseudo-medieval setting with medieval weapons. Most of the elements of the D&D game were inspired by myth that occurred during the middle ages, such as King Arthur and his knights of the Round Table. When people got more secular, and wanted to avoid offending people by portraying real world religions, they started grafting pagan deities in place of God and the Church into their setting to explain divine powers and clerical spells.
The thing about the real middle ages that I find interesting is that people believed in witches enough to burn people at the stake whom they accused of practicing witchcraft, but in their lives they never actually experienced magic themselves, they were quick to point their fingers at someone and call them a witch, but somehow, they were always brave enough to round up said witches and burn them at the stake without fear of reprisals by the so called "witches" themselves, so they believed at a certain level that those they accused were not actually witches, they just wanted an excuse the gullible peasants would accept so they could burn someone at the stake and take their property which they very much wanted, and get the Church's sanction for doing so, after maybe making a generous contribution to the Church and some Church official to buy their support.
I think there were two kinds of people, those who believed and those who went along with that belief because the Church was a source of political power, it was bigger than any single kingdom in Europe, so Kings had to tread carefully here, lest they be overthrown for offending too many lay people who believed in the Church and who thought the ruling monarch was a bit of a heretic. Others waiting in the wings who wanted to be king, would be quick to point fingers so they could gain the church's support and ursurp the throne.
The thing is, most people who lived in the middle ages were very religious, those who were not went through the motions so they would not be accused of heresy or witchcraft, and so stay safe from the Inquisition. According to the Inquisition, witches were all over the place, every little thing that could not be explained could be attributed to witchcraft. People in the church derived their power from it, the more corrupt ones defending their power base could order executions, if they could justify it on the pasis of someone practicing witchcraft, so you see the Middle Ages were a little crazy with witch hunts and people protecting their power.
I ask they question is what would be different if Magic were actually real? Not just any magic, but D&D magic? The World would have to accommodate itself to this fact and change their behavior accordingly, here magic is not just hearsay and an excuse for a witch trial. If their are real witches, they will not be burned so easily, especially if people were afraid of being turned into toads and actually were!
Basically, I am keeping to the flow of history, the Kings and Queens we know from the history books are in charge when we are talking about places on the Map of Europe, and the Mediterranean World, that means the three big religions are Christianity, Islam, and Judaism. There are a few pagans left, and to some degree the World is in transition though in Europe it is mostly converted to Christianity.
If I translate these beliefs into Game reality that makes God an overwhelming power in this world, but Medieval history does not contain a lot of acts of God, mostly just humans fighting each other trying to gain power at one another's expense, there has been plagues, that many have attributed to sinfulness and God's wrath, and Invasion by the Mongols and so forth. Insert D&D magic and monsters into this mix and it changes things somewhat. The Church and the Kingdoms have to accommodate this some how. That priests cast spells is accepted as semi-routine. No one bats an eye when a priest lays his hands one someone and heals their wounds, that is just a part of everyday life, not the "big deal" it would be in the actual Middle Ages! Wizards and Sorcerers cast spells and craft magic items, I have to alter this world minimally so society accepts this and does not go bat crazy every time some mage casts a spell. W
itch hunts are usually reserved for evil witches, and are usually led by other spell casters, and is truly a matter of safety and protection. Spell casters that go about their business and don't threaten the community are usually left alone. Wizards are out in the open, just as D&D suggests, they don' hide or form secret societies usually unless they are really up to no good! If someone sees a dragon, and it does not burn down the village, it is not that big a deal. If elves and dwarves come to a village to buy stuff, people don't usually go nuts over that, Orcs maybe, but this is a part of everyday life, everything else is based on historical Europe. Northern Africa is much the same. Unexplored parts of the World can be very different from what we know them to be, hence the elves in the Americas, they have to live somewhere you know!
Real World religions cannot be excised easily without changing what remains into something unrecognizable, so Christianity remains, because as you can see from those paintings, that really is the backbone of Medieval Europe. Magic and monsters can be added, but the belief system has to stay, and that way I can use existing kings and queens and cities as a backdrop. If I got rid of the Big Three religions, I'd have to replace history going all the way back to the early Roman Empire, and I'd rather not do that.
