: definitely far too easy on them.
If they are getting frustrated by puzzles / lack of progress, you can have the Fog Elemental attack them first.
Turning a puzzle into a combat is an almost surefire way to reduce the amount of boredom.
Don't rely on Players figuring a way out. Even a party of ingenius players have good and bad days.
eg. A Skill Challenge is going nowhere, FAST. Say it involves getting past a locked door.
Have an alarm goes off, a bunch of Guards come over and beat on the Players.
One of them has the key. Done Deal.
Generally, to get past the frustrating with the blindingly obvious, it should be something that you can just mention to them across the table, like "Do remember that there's a door leading inside" or "Please note that this is a port-city and there are probably ships that can sail across the sea." or "As mentioned earlier, there's a cave entrance in the mountainside.", don't count on it to move things forward when Players are getting frustrated. Second Case
:"Game mechanics wise about 3 turns until completion" - if the Players did not know this, you could have extended it slightly.
However, in this case I think the fight was fairly balanced, especially since they only needed to hit her to get a chance to disrupt the Ritual.
You can add clues like "You hear disembodied words being chanted from the air around you as you fight."
The Minions are not overly powerful, in fact in 2 rounds they should have been done with the battle, especially since they pushed the Guardian (Elite) into a 100' plunge. That's an Encounter for 3 characters and they were fielding 4.
In any case, I assume the Giant Air Elemental wasn't too strong as it wasn't a TPK. Given that as well, you're not harsh at all.
In fact a little lenient - I would probably have let the GAE tear a few Heroes down and then leave to terrorise whatever faction / people they were trying to serve, thus affect their reward and reputation. Alternatively, simply really nasty buffs and attacks after being Bloodied.
What might be unfair is IF they spotted her and simply couldn't hit her (and disrupt) because she was invisible, giving them a -5 to Hit. You could provide her to be blurred (Partial Concealment) after one party member notices her.
That was what my DM gave us when we were a Level 12 party of 4 going into a fight with TWO Solos ( we didn't know it was 2 Solos )
One of them was an invisible Demon and had At Will Dominate (Save Ends). When Bloodied he can do it Twice per Turn. It targets Will and both our 1 Defender and 1 Striker in the party has low Will. He always went for one, then the other, and only targeted the rest when the other two were already Dominated.
The other was a Dragon with standard Dragon attacks, and could perform 4 Attacks (3 Claws,1 Bite that deals ongoing 5) as a single Standard Action.
Before the fight started, he dropped us an unavoidable trap that all reduced our HP by... hmm.. 48 or so? We were all bloodied before the Dragon appeared.
Fortunately, at least once we managed to detect the Demon, he was considered Partially Concealed instead of Fully Concealed.
One of the most memorable Encounters for me, EVER
Perhaps a little Harsh, but hugely Memorable. And yes, that's what makes the game for me, and might make the game for your Players!