This was an interesting thought that occurred to me and I think would be a cool detail to add here or there throughout the more barren parts of the map. Obviously the main condition is if witches are lore accurate. Firstly I have to define what I mean by witches, as it is a pretty broad word. I think something closest to it would be the witches of the medieval times or the druids of Celtic religion. My idea would be small groups "covens" who fell under the influence of fallen maiar, made trades for power and the ability to perform on some level "magic", the maiar being remnants of Morgoth's time, still hiding throughout middle earth, maybe now under the control of Sauron. Or the witches could be groups of worshipers to Melkor, or maybe even Sauron himself.
Obviously these groups would be found only among men- Elves, Hobbits and dwarves are out of the question. (well I guess mainly just the elves) Also among men these groups would probably only be found among the remnants of the old inhabitance of Middle earth before the Numenorians settled it. People outside of the Edain, who dwelt there from the first age. The Dunlandings, and other wildmen spread throughout Eriador, possibly Bree folk? Anyways if witches covens or secret gathering places or whatever were added throughout the map it would be a pretty cool detail to find and explore.
Now obviously this all is pretty far-fetched speculation. Tolkien never mentions witches aside from the Witch King, and the time when Galadriel is mistakenly called a witch. I personally think witch king was an adaption from some Westron name (like many of the names in the story) made to create a bit more of an evil aura to his character, for us readers who are familiar with the idea of a witch.
When Boromir mentions Galadriel being a witch, it seems unimportant because it was a mistake, however it shows us that the people of middle earth were familiar with the term too, or at the very least the Gondorians, making it possible that these witches actually existed somewhere or were believed to exist.
But again, Tolkien never actually says there are actual witches in middle earth and if this was something we actually added we should think carefully and make sure it doesn't go against the lore in any way.
So yeah, please post thoughts on the subject if you have any. I think it would be an interesting idea, at least to consider, and a neat layer of detail to add to the map if we did it.