Good post nemo! Makes me think about stuff. A few comments.
I think it's always a good idea to be honest and up-front with your players, and discuss things before you start. Before every game of DW I run I explain that the game is probably a lot more lethal than they're used to. Encounters are not necessarily balanced, and that they need to be cautious. If you don't explain what they're buying into and then they can't harm something, it's very reasonable for a player to be frustrated. But if they know what they're getting into and complain, I'm not sure what to tell you.
In a play-to-find-out mode I'd be more inclined to have every conflict be theoretically winnable rather than to have decided beforehand, for example, that a given foe can only be harmed by magical weapons and if the characters don't have them then nothing they do is going to shave any of those 16 HP off. (Wondering whether others agree even with this stance for this game - maybe your prep tells you otherwise and the PCs need to Discern or Lore their way to the solution and come back another day because this fight this day is utter suicide).
I think this is where fictional positioning comes into action. Lets say you fight a monster that cannot be harmed by non-magical weapons. Something like a werewolf who heals any cut or wound not made by silver or magic.
The players (who probably don't seriously carry silver copies of every weapon) may not have a way to damage the creature, but they can drown it. It has to eat - you can also poison its food source. They could find out that fire may hurt it. The point here is that the strategy and tactics for defeating the monster may have nothing to do with hacking or slashing, but it doesn't make the encounter necessarily untenable.
And frequently it's exactly a case of leaving and returning. Or doing something to mitigate monster damage (like lighting the building it's in on fire) to keep it busy while you evacuate the village and buy time to go do research and return with something capable of defeating it.
If my amount-of-defy-danger assumption is roughly correct, I wonder what cues the game has or wants to be able to translate this to MCs. Are there tags that convey it? Or is a name like "Dragon" enough? As an aside while thinking about tags I'm wondering whether others would translate the messy tag as tacit permission to de-limb PCs as a part of a foe's attack?
There's a great fictional blurb next to every creature.
Also I'll quote:
p. 107
Messy: It does damage in a particularly destructive way, ripping people and things apart.How would you interpret that?
After chewing on this and running some more DW, a found myself in a session where two of the players were a little frustrated with a situation where I was indicating H&S was not a viable move in the current circumstance. They'd been able to use that move in all combats previously and now they were dealing with a foe that was too fast, intelligent and ferocious to be cut down by trying to simply step up to it and hit it with an axe. I had some ideas about how such a foe might be harmed but 1) The thoughts weren't fully formed/prepped (I didn't expect them to come after this thing after describing what it had done to an armed camp!) and 2) I didn't want to lead them by the nose.
I think that you have to get the rhythm of describing the fiction down right away. I usually try to put together a fight with an H&S block early when I run stuff to explain the whole 'fiction triggers moves' concept. A lot of people are trained (by every other game) to just say 'attack' and there is nothing that stops that. Once folks understand that this isn't the flow of the game always, you get less pushback.
All of this to say that with some players I think I'm going to need to run DW a bit differently than I might prefer. I don't really want to add hitpoints to monsters, so I'm thinking about some other possibilities and house rules that make "low hitpoint" legendary and scary monsters work better for me. I'm finding that if a DW party focuses on damage, they can really lay it on starting at 2nd level - there's a big difference between 1st and 2nd level in the amount they can do if they're permitted to go straight to their damaging moves in any given conflict.
If you feel you have no other choice, just slap +10 armor on them unless they can bypass it. Or let them do 12 damage and have the creature heal right up. It feels like cheating (I'd rather say the blade just bounces off the hide) but it's an ugly systematic solution to essentially something you should probably talk to the players about outside the game.