Although they use a wide variety of mechanics, most fantasy role-playing games have remarkably similar view of magic. I term this view "scientific magic". This doesn't mean that magic follows the laws of science as we know them. However, magic is a reproducible force that fits with modern scientific viewpoint and culture. While scientific magic systems have their place, I think there should be more games with non-scientific magic systems... magic evocative of myth and folklore, as well as fantasy fiction which draws on myth and folklore, like J.R.R. Tolkien or Charles De Lint.
Various RPG systems try different mechanics in an effort to make their magic feel more "magical". However, I feel that most of these simply alter the mechanics almost at random. The problem is in how magic is conceived of in the first place, not in the stats and die rolls used to implement it.
In order to create a non-scientific system of magic, you need to consider the basic principles on which magic works. As a designer, you should think about what magic means in your campaign world before you start defining stats or die rolls. The typical FRPG system makes a number of assumptions:
Note that none of these assumptions is neccessarily "wrong", nor do all five of them need to be broken for a system to have a non-scientific feel. The important thing, as I see it, is just to question these assumptions before putting them in your designs.
RPG magic systems can roughly be divided up into "fixed spell" and "freeform" mechanics. Fixed spell systems are often highly mechanistic, where the operation of each spell is exactly calculable. Freeform mechanics, on the other hand, call for the GM to judge the difficulty of a spell based on little information as well as a large degree of randomness.
Neither of these, however, is "mysterious". A mystery means that no pattern is obviously visible -- but there is a hidden pattern. For a magic system to be mysterious, there must be hidden patterns which the magician character does not know at first, but which can with effort be discovered. In a game, this means that there must be either hidden variables or even hidden rules. An extreme of this would be that the GM secretly designs the magic system and only lets the player learn it a bit at a time (i.e. completely hidden rules). However, mystery can be injected by having hidden variables. i.e. How a PC's magic works depends on factors which are defined by GM, but which the player must deduce from other clues.
In a given magic system, chance of success of a spell might depend on what type of spirits inhabit the place where it is cast. There is no spell which simply answers this. The magician would have to deduce from other clues to find this out. The spirits might follow the traditional humors: choleric, melancholic, sanguine, and phlegmatic. The spirits of a place would subtlely influence it according to their nature. Thus, by observing and learning the history of a place, the magician could guess what types of spirits inhabit the place.
Discovering hidden variables of magic should not be the main focus of adventures, unless that is the aim of the campaign. However, they should form an important subplot or subplots. They must must be designed like any good puzzle or mystery. There should be enough variety that it is not totally linear, but not so many possibilities that it is too daunting.
In a certain magic system, the GM secretly assigns a distinctive set of traits to each magician PC as he is created. Some may have blatant effects, but which character caused the effect is never obvious. The player will only slowly learn the true nature of her character's magic, which should influence what further abilities are possible.
One can easily go overboard with making magic mysterious. The important point is just to consider having some mystery to magic, rather than assuming that all variables and rules have to be open to the players.
RPGs tend to say that the world works exactly the way that modern science describes it, except for magic. Magic is required for anything that works differently than modern science -- and conversely magic is never involved for things which science can explain. Thus, the RPG system is designed first to simulate a non-magical world, and then a neatly self-contained extra set of rules is tacked on to handle magic.
This approach can make it easier for players to understand the game-world. Since they are modern-day people, they can take their scientific viewpoint and just add a few new rules. However, the concept of magic really comes from a pre-scientific age. From a pre-scientific viewpoint, magic is not a thing apart from Nature. Indeed, many things in Nature are inherently magical. Magic is integral to explaining why it rains, the beating of your heart, and many other things.
For example, many magic systems define spells like "Detect Magic" or "Anti-Magic Field". If no magic is detected, or if all magic is prevented by a field, then things work "normally" (i.e. according to modern science). The idea that things work normally without any magic is contrary to a pre-scientific view. A sorcerer can detect and cancel other spells, but taking away all magic does not make sense.
In order to break this assumption, I think an RPG has to toss out the idea that there needs to be a neatly self-contained "magic system" which is independent of the rest of the rules. Magic needs to be a set of rules which mix with the what we often consider normal systems. This may be difficult to conceive of, simple because the assumption is extremely pervasive. Some more examples:
Example 2: Most RPGs define a non-magical healing skill to cover things like bandages, herbal poultices, and other things explained by modern science. This is considered totally unrelated to magical healing. To a pre-scientific view, this division makes no sense: most scientific healing techniques would still be considered magical.
Example 3: Most magic systems define enchanting items as taking ordinary, non-magical items and adding a property of "magic-ness" to it. Thus, a sword might be well-crafted out of superior steel, but it is not magic. In pre-scientific views, though, crafting of steel is itself a magical process. The hardness of the metal is part of the magical-ness of the sword.
In general, RPG magic systems view magic as something ephemeral. Effects are rarely permanent or even long-lasting. Even when they are, the permanent magical effects are vulnerable to "dispel" or other ways of cancelling them. This often stems from the view that magic is "unnatural". Thus, in a scientific magic system, it takes continued magical exertion to keep things from reverting to how Nature (aka science) intended.
In myth and fantasy, there is a common type of magic which is about enlightening a person or perfecting a thing. Historical alchemy is not solely about turning lead into gold, but also about the alchemist achieving ultimate enlightenment or perhaps immortality. This sort of internal magic is frequently ignored in RPGs.
Example 4: Many RPGs handle "Speak with Animals" as a spell. With this, the magician casts a spell and for a limited time (say a few minutes) can speak with animals. During that time, the effect could be dispelled or cancelled by various means. In myth and legend, if someone can speak with animals, they can just do it. It is simply a skill they know. This could be put in an RPG simply by treating it as a more major ability that is usable at any time.
This doesn't mean that your game system has to be redesigned from the ground up solely for magic. However, some "normal" sub-systems should be changed to reflect the magical-ness of the world. Many natural phenomena are commonly regarded as being magic to some degree. Highly magical events include eclipses and giving birth, for example. Lesser magical events include weather, ironworking, chemical reactions, and diseases.
One option to do this is to redefine some skills to account for magic. Thus, "healing" would be a magical skill -- at low levels it is like a mundane healing skill while at high levels it has effects that are clearly magical. Another example... Rather than having "normal swords" and "magical swords", each sword simply has a bonus which represents its quality, and may have special attributes like "finely balanced" or "troll-bane". A very skilled smith -- or a smith aided by a magician -- will make a sword with a higher bonus. Spells can harm the sword and thus degrade its quality, but you cannot attack the magicalness of a sword separately from the sword itself.
Another option is the reverse... Use magic mechanics and use them for activities which are often considered mundane. A notable example in published RPGs is Runequest, where all disease is treated as a disease spirit attacking the victim and is fought off like other spirits. As an alternate example, "charisma" could be considered a magical effect. Perhaps a magicians stored magical power is literally his charisma score. As he loses power, he becomes less charismatic.
A typical fantasy RPG magic system consists solely of rules for the useful magical abilities of player characters (PC's) and their potential opponents. Thus, if the party has no PC magicians and are not facing any magician opponents, the magic system can be ignored. In myth and folklore, however, magic often happens without anyone casting deliberate spells. There are magical events such as omens, visions, destinies, lucky objects, and miracles. There are also magical places and magical times. Lastly, there is magic of circumstance. For example, if someone dies in certain circumstances he may return as a ghost to haunt his killer. This isn't because the character had the "ghost" magical ability, it just happened because of the circumstances of his death.
In terms of RPGs, breaking this assumption means thinking of magic as more than just spells cast by PC's and NPC's. You can design magic into the game-world by making magical events, times, places, and things. Magic can also feature in adventure design. Adventures in a mythic-magical world should reflect the magical principles which are at work.
Example 1: In a fantasy game-world with many spirits, the GM decides that spirits have effects on their own besides being a source for magicians. A variety of common rituals done by everyone have in-game effects. For example, each house generally have household gods symbolized by small idols. As long as the household gods are properly appeased, the house gains some measure of protection.
Example 2: In a Renaissance game, the GM decides that each adventure is going to have a canonical tarot reading. The GM can do a random reading to help think up an adventure and/or set cards the way he likes. This reading is written down and becomes the guide for omens and divination during that adventure. A successful tarot divination roll will show this reading.
Depending on the sort of magic which you want, magic can show up in different ways. Magic times might be at equinoxes or solstices. Magic places might include standing stones, mountain tops, or sacred groves. Magic rituals might include marriage, blood oaths, rites for the dead, coming of age, and consecrating ground.
You can also change the deliberateness of magic. Many RPGs tend to assume that magic is a professional skill, which is learned in a mage's guild or other organization. However, in myths, the wizard is often a solitary figure whose magic is an inborn talent -- which can be a curse as well as a blessing. The archetype of the wizard is often a mysterious hermit, who shuns and is shunned by society at large.
Most RPG magic systems have the idea that there is a magical energy ("mana", "vis", "power",...) that is used up in casting spells, and is then recharged over time. This is often central to game balance, as the system gives magician PC's very powerful spells, but limits them to only a few uses per day. The mechanics treat it as energy which follows scientific principles. This is inherently very different from magical power in pre-science stories.
For example, several games use the term "mana" for their magical energy. Now, "mana" is a genuine Polynesian term for a variable property of divinity or sacredness. Polynesian mana is very different than conserved energy, however. For one, it is not lost due to use. Indeed, success is seen as proof of strong mana being present. Instead, mana is lost by breaking of "tabu" or by defeat.
Breaking this assumption means first of all ignoring the idea that spells need to be powered by magical energy. This may mean re-thinking how you balance PC magicians, and what niche they will fill in a group. Magicians can be limited by having a narrower range of abilities, by taking a long time to cast, by needing hard-to-get ingredients, by requiring concentration, by being risky to cast each time, or simply by their spells being less powerful.
Example 1: In D&D, mid- and high-level wizards can cast a giant explosive fireball which is limited to a few times per day. Clearly taking away that limit is unbalanced, but the only reason is because the combat spells were made overly powerful. If instead combat spells were more on the level of what skilled fighters could do, then unlimited spell use would not be unbalanced. Spells might be more subtle or narrow in their usage.
Beyond game balance, though, there is the mere concept that energy does not need to be conserved. This is a very ingrained to scientific thinking, so deliberately breaking it by itself can give a system a less scientific feel. A good example (detailed in the next section) is interaction of the metaphysical and the physical.
RPG magic systems tend to make magic physical rather than metaphysical. For example, in myths a curse might only be by "true love" or a test might only be passed by one who is "pure of heart". In RPGs, this tends to be reduced to more tangible, mundane quantities, such as one's level, class, etc. This is understandable since it can be difficult to judge whether a given PC is "pure of heart". Unfortunately, this also strips magic of an essential quality.
At the heart of mythic magic is the idea that intangible things like morality or purity have physical effects. If you want to retain this flavor, you should strive to put in such effects into the magic of your game. For example, in many myths, a moral test is at the heart of a magical advancement or a magical undertaking. If the character passes the moral test, she accomplishes something different than if she fails. However, both results must have an outcome which is in some way desirable to the character. The key to designing an interesting moral test is that there must be reasons for each side. If the PC is asked to choose between adhering to his faith or becoming an evil pawn, the test is worthless.
In one magic system which I ran, any of the magical characters had the ability to freely gain a power of limited mind control, such that whatever the character said had some supernatural influence. This also opened up further opportunities for related magic powers. The catch was that this power could never be turned off. The character could never again speak freely with her friends, because her power would act on them. If others learned of the power, they would (rather justifiably) be extremely suspicious. In a time of stress, one of the PC's took this power and used it to good effect to help her friends. However, it caused her many headaches thereafter.
Most commonly, RPGs tend to reduce moral qualities to fairly rigid codes or the dogma of a particular god. To the priest of a god with tangible powers, sticking to the code is a no-brainer since breaking it will strip one of one's powers. For it to be a real moral test, there must be a valid temptation.
Moral tests are in some ways easy in that they can be codified into only two (or at least only a few) results. Each choice then has distinct magical results. Other intangibles are harder to apply to a game. i.e. How does the GM decide whether the attraction between two characters is "true love"? Applying these can be difficult, but there is a major effect in the feel of the magic.
In one magic system for a particular campaign, the chance of success for any spell was inherently based on how much the magician knew about the specific target. i.e. Casting a spell one a stranger was much more difficult than casting a spell on a known enemy or friend. I implemented this by having a scale from 1 to 20 for how familiar the magician was with any given thing. This then went into the formula for success along with other factors like magic skill and so forth. I had a rule of thumb that skill rolls could gain you X points over time, but in-game actions would also change it. This often made for judgement calls, but it was certainly playable.
What sort of intangibles you want to incorporate into your magic is an open question. Just remember the type of intangibles you choose will influence the flavor of your campaign. Having true love be a key to certain magic will make the campaign tend towards romance, for example.
One point to remember is that in medieval and ancient history, magic is almost universally closely tied to religion. For example, the main reason why the Christian church was so opposed to witchcraft was that it generally represented pagan beliefs. Alchemy and hermetic magic were thoroughly tied up in Christian theology, while in turn Qabbalah was obviously tied in with Judaism. Even if your magicians are not priests, magic should be understood in a basically religious worldview. The nature of the soul and similar issues should play a part in magic.
The point of this article is not to say what magic should be. If you like any of the ideas suggested, go ahead and work with them. But use whatever other ideas come to mind as well. My main criticism of existing magic systems is that they are too much alike, imitating each other rather than branching out to new ideas.