Make sure everyone at the table is playing the same game
The very first thing that strikes me is that you want to run a political intrigue mission while they want to just roll dice without necessarily thinking too deeply about their choices.
These are two playstyles that are at odds with each other. Based on this and the linked questions, they want to play a hack and slash. If that is their taste, that is perfectly fine. There's nothing wrong with just wanting to swing your sword. The question is, are you willing to run that?
Evaluate your campaign if it has these elements
The following advice rests on the fact that your players have agreed that they want to play the game you want to run, which is a campaign where challenges are not straightforward, and creativity is a requirement.
Do your Player Characters have any motivations?
Everyone in an engaging and exciting narrative has something they want, but they can't have. They are driven to gain that thing, whatever it is, and that fuels them so that they can drive the story forward in turn. Do your player characters have them? And if they do, are they cool, genuinely engaging motivations?
It's not enough to say "my character is an orphan and he wants revenge on his parents' murderers." I mean, that's actually a fantastic motivation, but it should have more detail than that, and the details should be the kind of things that your players are excited about.
What about: "my character is an orphan because my parents owed Torbor Longbeard money, and when they couldn't pay up, he tried to take our house and everything we owned, but they tried to fight back."
Or what about: "my character is an orphan because I poisoned them to inherit the throne, but Lilian Stormwell discovered my plot and exposed me, so now I want to get her back."
I once ran a game for someone who suffered from a chronic disease, and he basically couldn't do a lot of things by himself. So his one fantasy was to be a noble, honorable, capable, handsome, and well-respected general. And you know how he reacted when I let him have that fantasy? He became very engaged in the story. He tried to solve every problem I threw his way no matter how hard it was. He bought into the fiction completely, and whenever he couldn't solve a problem, he would get frustrated, but he had fun regardless. He didn't blame me. He would tell me at the end of the game how much fun that was.
Get your PCs some motivation. If they don't have any, brainstorm with them. This is step one.
Are your Player Characters' motivations grounded in your fiction?
Simply getting your players to have characters motivated to do something is not enough. You might have a character whose motivation is to sleep with every woman in the world, and that's a valid motivation - but they would be out of place in a campaign about rallying the Forces of Light to defeat the Dark Lord, maybe except as the designated comic relief.
You want to tell a story. So you decide on what that story is, who are the main movers and shakers within in, and tie your player characters into it. They don't have to be central to your main plot, but they have to match the tone you're going for.
If you're running a political intrigue campaign, then their motivations should be somewhere that it won't take more than one step for you to connect them to the story you want to tell.
If your campaign doesn't have a backbone plot, if it's not about something, then work on adding one in. How can you ask your players to put in the work when you haven't done so yourself?
Additionally, make sure your player characters are themselves grounded in the world. It's so easy to make an orphan who comes from a town they destroyed because then you don't have to write anything substantial. You become a drifter in the plot, floating along with the tides but with no real stakes and no connection to anything.
Give them a mentor, wife, child, sibling, or - yes! - even a parent that they care about. If possible, align this anchor with who your players are in the real world, so that they can more easily slip into the fiction of becoming the character they're playing at the table.
Anchor your player characters and your players to your fiction. This is step two.
Did you make failure interesting in your puzzles?
Simply including a chance of failure in a task doesn't make it fun by itself. You can, in fact, create an entire puzzle that's impossible to fail, but twist it so that the win is still engaging. You can make a challenge complex but without depth, and then it would still be boring.
Do the characters have something to lose if they fail? What are the stakes? It sounds like though the players failed, you still rewarded them with a lot of stuff. So what does it matter if they couldn't solve it? It feels like an artificial wall that the DM is putting in their way. It doesn't feel like they failed, but it feels like you want them to step to the left, turn around, jump on one leg, and press X before letting them through.
One thing any artist, actor, writer, or creative person in general wants to achieve is to "melt" in the background, to blend with the work so seamlessly that the hand of the author isn't visible. Try aiming for that.
One approach you might want to try to achieve this is to never say "no," but to say instead "no, but." Describe their failure and then create a circumstance to make it worse. Reply to "Do I see any traps?" with "No, but because you didn't see them, you triggered them by accident. Make a Dexterity saving throw."
My personal favorite approach is to exploit the characters' motivations. Place them in a genuine dilemma. To accomplish one thing they want, they have to sacrifice another thing they love. This is...
(SPOILERS TO AVENGERS: END GAME)
Thanos sacrificing Gamora to gain the Soul Stone.
or...
(SPOILERS TO GAME OF THRONES)
Ned Stark choosing to lie about the way Robert Baratheon died and break his code of honor to save his children from persecution.
Define the stakes. What do they have to lose? Do they care about what they have to lose? If the answer is yes, then you're doing good.
In conclusion...
Make sure that:
You are all on the same page, that you all want to play the same game
Your characters are properly motivated
Your characters are properly grounded to the world
Your challenges are innately interesting and engaging
At the core of this, make sure your players are buying your story. Sell the narrative effectively, and if you do that, your players will be engaged, even if they keep failing your challenges.