Saucepen Man supernatural elves re (leaving whole witchcraft issue alone for a while):
From mortal point of view, yes, maybe they must have been thought of as supernatural (even at that time)
On the other hand, no, neither elves nor even Valar seem supernatural at all. By nature I mean not a nearby wood and a river , the Nature in question is the whole of the universe, created in the Halls of Eru. It is arguable that Ainur were before time and creation of the world, and therefore must be supernatural, but I was talking about Valar, who entered the World because they loved it and are henceforward bound by it. Ainur who did not do not meddle with the world afterwards. So, the argument is - whatever is inside nature, is natural, regardless its abilities of walking thrugh walls or high speed travel or enchantment
There is a whole of Osanwe-Kenta to consult with (as to restrictions following such an entrance and imposed by 'being bound with the history of the world', i.e. impossibility to interact with the substance of the world if not at least 'clothed' in a body etc.) Check out Jallanite's entry
here It deals mainly with the possibility of flight for the incarnate Maiar, but can give an insight as for 'supernaturalness' as well.
Therefore, I conclude, that there is no magic (if defined as something supernatural) in ME, but mere application of natural faculties