Hi, wow this is a really great thread. Too bad I didn't find it earlier. I want to preface all of these remarks by saying that they are meant to apply to Medieval Catholocism c. the 12th and 13th centuries (when the Crusades were at their height), and not in any way to the doctrines of modern Christians of any stripe, Catholics included.
First of all, treating Satan as a diety is, as many have suggested, strictly speaking, not in keeping with orthodox Catholocism. Satan is a demon, a fallen angel. Among other things this means that, unlike God, he is neither omniscient, nor omnipotent, nor omnipresent. So, Satan cannot directly grant spells, nor is he automatically aware of the events that transpire in the world. He would need a network of lesser demons, and perhaps also human agents, to influence events and to keep him informed.
As far as God granting spells, many contemporary texts seem to suggest that people of extreme piety (Sts. Bernard and Francis, for example) could, in fact, pray to God for a miracle with a reasonable expectation of success. The catch is that even these extraordinary individuals did so extremely rarely, nothing on the level of a cleric getting multiple spells per day. However, since this is D&D and not Harn, after all, this could probably be fudged in order to provide for a more fantastic experience.
Another thing that you might want to note is that the average person's access to miracles came not through living holy persons, but through the shrines of dead Saints. People who were sick and injured would pray at these shrines for healing. So, you might want to include something like this in your campaign.
As far as arcane magic goes, contrary to what several people have said, there is precedent in medieval thought for the existence of magic that is not demonic. The idea of natural (as opposed to demonic) magic was adapted by Christian thinkers like Grossteste and Roger Bacon from Arabic, Muslim scholars such as Alkindi. My impression (I'm not an expert in this) is that this "natural magic" could be used to do things like control the four elements and plants and animals, and also to manipulate any kind of physical matter (which, from their point of view, was composed of varying ration of the four elements). Demonic magic, on the other hand, would be anything involving necromancy, illusion, enchantment, and probably divination. Both would rely upon words of power, with the difference being that natural magic uses words that, somehow by their very sound, cause resonances in the natural world (this is putting it pretty loosely, but you get the idea), whereas demonic magic simply calls upon various demons.
drquestion