SLTE
Dreamer
As with pretty much everybody else in the thread, I agree that magic is far from compulsory in fantasy. In some stories it's just not gonna fit, so why risk messing up a perfectly good story just to fit with expectations?
I don't think authors really need to worry about the categorization of their work, at least not while they're writing them.
Take, for example, Margaret Atwood. Her novel "The Handmaid's Tale" takes place in the future. For that reason, it is sometimes classified as "science fiction," something the author has opposed. Other than the fact that it takes place in the future, there is little or nothing that deals with issues of science in the book; it's a political story, not a story about science or technology's affects on society. That being said, the debate over whether "Handmaid's Tale" should be classified as SF or not sometimes overshadows the author's intent and the work itself.
My point is that I don't think how the book would be classified -- its marketing category -- ever really occurred to Atwood as she was writing it. The setting was simply a means of creating a setting in which she could tell the story she had in mind.
Likewise, you're interested in telling a story that shares some elements with other works that get lumped into the marketing category "fantasy." You can't really worry about that. You need to tell the story you want to tell. At least, that's true as a writer.
Something you may need to keep in mind is that publishers really like works that fit neatly into their preconceived marketing categories. They know what to do with those. If you write a book that very clearly fits into the Tolkienesque fantasy category, publishers interested in that sort of thing will know how to market it and to whom. The more your work strays outside the various niches defined by publishers and booksellers, the more difficult it will be to get an agent, if you don' t have one already, or a publisher.
While you have to recognize these sorts of things, you shouldn't let it force you into a direction you don't want to go in. Write your story. Don't worry about the business details until they become an issue.
If there is no magic and nothing supernatural, is it still fantasy? Can you have an imaginary world with imaginary creatures and leave out the magic?
Not that my opinion is worth a wooden nickel---I believe that magic is far from mandatory in fantasy---that's the beauty of it.