As far as I know, there once was magic in Westeros, just as there once were dragons. For example the Wall is said to be built with the help of magic. I don't recall anybody sneering about it, but I get the picture that people "know" and "acknowledge" there once was magic.
When Stannis releases the Onion Knight they discuss the things they witnessed and Stannis concludes that the Lord of Light must be real. At least in the TV show, the discussion is concluded with a (probably rhetorical) question how all this can be if the Lord of Light wasn't real. I find it rather strange that people never even suggest the return of magic. (Especially after they seem to have established a very peaceful co-existence of monotheistic and polytheistic beliefs, but I'm straying ...) With everything I think I know, I'd rather say with the "church" of the Lord of Light magic finds its way back into the world.
When Thoros of Myr told Melisandre, that the Lord of Light had brought back Beric Dondarrion from the dead 6 times, she was startled and said: "you shouldn't have that power". The interesting thing is, that for the half drunk Thoros, it is crystal clear, that he merely prayed and the Lord of Light did the work. Still, Melisandre seems to know that resurrection is something the priest does/did. To me it's clear, that she is more into everything concerning the Lord of Light than Thoros has ever been.
Could it be, that Melisandre is actually a witch who is very aware of it and the nature of her powers and merely uses the religion of the Lord of Light to train, explain and (re-)establish magic in the world, but doesn't actually believe in R'hllor?