I've decided that my campaign is going to be about dark forests and swamps and the supernatural beings that inhabit them. Looking at European fairy tales, my impression is that perhaps the major threat that underlies everything is unpredictability. Fey creatures follow strict rules, but their rules don't seem to make any sense. If you learn some of their rules you can use them to gain some power and control over them, but there is always the threat that you unknowingly make mistakes that grant the fey great power over you.
it's not the fey themselves who follow strange, barely understood rules, but also the land itself. Things just happen and you can't expect to get any explanation how they are possible. Talking trees and animals? You just have to roll with it. It also extends to the powers of fey and witches. When they are angry enough, they can speak curses that are very far reaching, like making everyone in a castle fall asleep forever, or turn large groups of people into animals.

Generally speaking, I would say that in such a campaign, magical phenomena and powerful curses don't need to have any game mechanics. They just are because the GM decides it's appropriate and it doesn't have to follow the rules for PCs casting spells at all. The problem is that unlike in an already existing story, the actions of the heroes aren't always what best fits the story, but it is up to the players to come up with something that they think might possibly help. And when things are completely unpredictable, they can't make any meaningful decisions.
So I think that at the very least, the unlimited potential of fey and witches should not apply to combat. You can't have a fight in which the opponnent can just instantly heal or be immune to everything, or the PCs will just drop dead or magically frozen at a whim. If a fight breaks out, then the rules of combat have to apply to all combatants. Of course the supernatural enemies can have special abilities, but they need to be clearly limtied abilities. Even if they players don't know what they are.
It also doesn't mean that the opponent needs to be easy to beat. What I think would be very appropriate is to have the big enemies be significantly stronger than the PCs, but also give them a significant weakness that tilts the odds in favor of the players. For that to work, I think it's best to have the magical enemies feel unthreatened by the PCs and not make any direct moves to kill or restrain them. A fey lord can simply have the PCs be unable to leave the castle or the valley and keep them trapped but roaming about freely until they do something that causes real damage.

A problem that I still see is how to avoid Deus Ex Machinas. If the magical enemy has a weakness that the heroes can exploit, it's probably a bit underwhelming if some NPC just tells the players what they have to do, as is actually very common in fairy tales. How else could the players find out how to harm a magical creature and negate its powers over them?