In "real world" context, I think the Key of Solomon is a great reference point. The premise is that King Solomon had all of the demons under his control. Here's an excerpt from the Wikipedia article on The Testament of Solomon, a pseudepigraphal work written before the 6th century:
When a demon named Ornias harasses a young lad (who is favored by Solomon) by stealing half his pay and sucking out his vitality through the lad's thumb on his right hand, Solomon prays in the temple and receives from the archangel Michael a ring with the seal of God (in the shape of a hexagram having the name of God inscribed within) on it which will enable him to command the demons (c.f. Seal of Solomon). Solomon lends the ring to the lad who, by throwing the ring at the demon Ornias, stamps him with the seal and brings him under control. Then Solomon orders the demon Ornias to take the ring and similarly imprint the prince of demons who is Beelzeboul/Beelzebul.
With Beelzebul under his command Solomon now has the entire race of demons at his bidding to build the temple. Beelzebul reveals he was formerly the highest ranking angel in Heaven.
The Key of Solomon is a grimoire which describes how to go about commanding the demons that Solomon put under his control by invoking the name of God. Here's a tidbit on how to become invisible:
OF THE EXPERIMENT OF INVISIBILITY, AND HOW IT SHOULD BE PERFORMED
If thou wishest to perform the experiment of invisibility, thou shalt follow the instructions for the same. If it be necessary to observe the day and the hour, thou shalt do as is said in their chapters. But if thou needest not observe the day and the hour as marked in the chapter thereon, thou shalt do as taught in the chapter which precedeth it. If in the course of the experiment it be necessary to write anything, it should be done as is described in the chapters pertaining thereto, with the proper pen, paper, and ink, or blood. But if the matter is to be accomplished by invocation, before thy conjurations, thou shalt say devoutly in thine heart:—
SABOLES, HABARON, ELOHI, ELIMIGIT, GABELOY SEMITION, METINOLACH, LABALITENA, NEROMOBEL, CALEMERE, DALUTI, TIMAGUEL, VILLAGUEL, TEVEMIS, SERIE, JERETE, BARUCHABA, ATHONAVEL, BARACABA, ERATICUM;1through him by whom ye have empire and power over men, ye must accomplish this work so that I may go and remain invisible.
And if it be necessary in this operation to trace a circle, thou shalt do as is ordained in the chapter concerning circles; and if it be necessary to write characters, etc., thou shalt follow the instructions given in the respective chapters.2
Here we have the ingredients I spoke of in the Anatomy of a Spell. There is the name of the spirit being invoked, the power (God in this case) through which you command the spirit, and the task you want the spirit to accomplish. There is also the obscure reference to other "instructions" that are elsewhere. In other words, you can't just cast this spell without already knowing a whole lot more about magic.
The interesting thing about this "spell" is that it does not contradict "religious belief" in its broadest sense. This is not "witchcraft" in the way witchcraft was understood in the middle-ages, which was making a pact with the devil to obtain power. This is using the name of God, just like Solomon did, to command spirits.
Regardless of the actual history of witchcraft and any contemporary views on it, the point here is to put this all in game perspective. A magic user and a cleric are not at odds with one another. They just get their powers in different ways.
In my game, "magic" closely resembles the structure from the sample above from the Key of Solomon. So what then of cleric spells? In Cleric as Prophet and Saint I suggest that the Cleric is more of a miracle worker than a spell caster. Thus is seems to me that the cleric need not know the names of the spirits who control such things as invisibility. Rather, the Cleric prays to the power-that-be (god) who controls the spirit who controls invisibility, and asks that he be made invisible by divine grace. Then presumably, the cleric's "guardian angel", or what have you, passes the request up and down the chain of command, and the very same spirit who was commanded directly by the magic user is now commanded by his superiors to make the cleric invisible.
Is all of this a bit too convoluted and unnecessary to your game? Perhaps. But having a basic understanding of how magic vs. miracle works in your world can give things a more consistent feel and raise some interesting questions.
If "miracles" are granted to the few, the proud, the Clerics, what then of the simple priest who has no such powers? What if this simple priest is ambitious, or is elevated to a position of power within the church and feels the pressure to come up with some "miracles". Might this priest not start delving into "magic", so that he can appear to be walking in the grace of the gods? This type of priest would fit in well in Shatterworld. Corruption can work its way up through "the church", and many priests who are believed to have divine power might instead just be monkeying with magic.