Now this is a question for me. I was the fantasy/sci-fi correspondent at the bookstore where I worked.
Anyway, from the sounds of your question, I would say you’re looking for a much more European definition of magic. Most mangas/anime base their roots in Japanese mythology, which is quite a bit different, so that might not be the best place to look. However, there’s plenty of other literature that I can recommend:
1) The Merlin Conspiracy, by Diana Wynn Jones. It has a very classic look on the whole idea of the fae, and similar mythological traits to king Arthur’s time. I was skeptical at first, but I really enjoyed it.
2) If you’re looking for the really arcane, you can try The Elric Saga (not to be confused with the Elric Brothers of Full Metal Alchemist). A series started by Micheal Moorcock in the 1960’s, it takes an extreemly aged and archaic stand on the whole ‘rules of elemental creation’, and the bonds that unite man and god. It might be thick reading, and gets very weird at times, but it might be worth looking into.
3) My personal favorite author is a British novelist by the name of Neil Gaiman. If the name sounds familiar, it’s because the new movie Coraline was originally a novel by him. His is a much more modern approach to magic, and he tends to blur the lines of fantasy and reality with no real definition, but writing style is fantastic and his presentation is spot on. I recommend both Anansi Boys and Neverwhere to start with.
As far as anime, I would recommend maybe Kamichu (which is about a girl who turns into a god for no apparent reason, but is really more about growing up than anything), or maybe The Melancholy of Haruhi Suzumiya (the details of which I can’t even begin to describe. They’re not exactly what you’re looking for, but you might like them anyway. You should also look into Miyazaki’s movies if you’re not already familiar with him, be cause he’s become very fascinated in that area recently as well.
Here’s the first episode of The Melancholy of Haruhi Suzumiya for all interested. Enjoy!