Jacqueline Carey's Kushiel's Dart series has almost no magic.
Greg Bear's Songs of Earth and Power has some very strange events, and few of them are termed "magic" in the book (he uses "power" instead), but they are the result of the place where much of the action occurs, and not due to some conjuring of spells by some wizard or mage.
As one who ordinarily prefers science fiction to fantasy, I am not enthused about reading fantasies where magic is the predominant plot element, or where it is a requirement for the success of the main character's quest. Such stories as the King Arthur legends (with Merlin), Lord of the Rings, etc, fall into that category for me.
It occurs to me that a fantasy about mystical happenings, strange and unexplained events or creatures, and the like, which cannot be explained in some scientific or even quasi-scientific way, involve magic in some fashion. On the other hand, stories set in alternative realities, worlds, histories, are certainly included in the genre "Fantasy" (some are included in the genre "Science Fiction" too, but not so much).