I have been GMing a game for a few months now and all in all it has been a ton of fun. My party has just gotten done closing down a portal to Limbo that was being held open by a death slaad and allowing for a slaadi invasion of a coastal village. Overcoming incredible odds and some needing to face tragic sides to themselves in the form of visions received on the plane of chaos they were victorious. The village was incredibly thankful and there was much revelry and reward. Magic items, riches, and praise were heaped on their saviors.
I tell you that to tell you that I'm not out to bully my players, I am out to tell a rich and satisfying story. The gist of it is that after this Slaad campaign they entered a part of the story that is supposed to ground them a little bit. I'm not taking anything from them or anything like that, but they've encountered some of the higher ups of an enemy army. They are interesting characters with their own motivations that go against a lot of what the party stands for.
More importantly, they are stronger than the PCs. I always keep a continuation of my story open whether the party wins or loses, and they know that, but suddenly they encountered a threat they couldn't defeat just by fighting like they normally do and the players just suddenly got incredibly bored and frustrated.
I'm of the school of thought that Mary Sues are boring and surely the same would apply to characters that can just wave their hands and make problems go away. But instead of thinking of escape or unconventional tactics my players basically just gave up and started robotically going through the motions of wait for turn -> basic attack -> done essentially just waiting to be killed.
The villains were pulled directly from one of their back stories and have been hinted at several times over the course of the campaign, one of the characters even met them and shared a drink before they knew they'd be at each other's throats. There was a story hook and the party was incredibly invested prior to the fight. I even designed the enemies to be sort of a dark reflection of a couple of the characters, including the fact that they only used powers or abilities that were also available to the party.
And yet all that in place and my players spontaneously lost all interest in the story and thought I was being unfair and railroading them into a scripted death even though the only option that was no longer available was beating them in a fair fight.. hell even that could have worked out if the rolls were good. So my question is, how on earth do you write an encounter where the players aren't supposed to come out on top? Because I feel like I've done everything right, but obviously not.