I was just about to leave a comment on Bright Cape Gamer's post on the most recent round of Hearthstone heroic encounters when I decided I my comment was going to get too damn long. I've done just a few of the heroic encounters so far, and I agree with the assessment that they are easier than they used to be, but I guess I have an issue with the whole idea of making a Hearthstone encounter "hard".
What does it mean for something to be hard? In Hearthstone it seems to mean two things: 1) Having to come up with a good strategy and build a deck to execute that strategy; 2) Restarting the game over and over until you get the right cards at the right time. (1) is fun, (2) is tedious, but unfortunately, you can't have (2) without (1).
Hearthstone is not an I Wanna Be The Guy fangame. It's not a game where you can face a challenge that is "Play on the razor's edge of human skill for 6 minutes." The moment to moment decisions you make in the game tend to be extremely straightforward, and the game is heavily governed by randomness.
The pinnacle of this kind of encounter was the Grim Guzzler heroic from Blackrock Mountain. In that encounter each turn your opponent uses their power to put two minions from their deck and one from yours onto the battlefield. If their deck was full of River Crocolisks then this wouldn't be hard, but it is full of pretty big dudes, so you can't just get minions that out muscle theirs. I didn't have all the cards I might have liked but I did have Kel'Thuzad, and I did have the rogue spell Gang Up from beating the Guzzler on normal difficulty. So I built a deck of 29 spells and Kel'Thuzad and simply restarted the game until I could Gang Up on my second turn. When you get a Kel'Thuzad every turn, you don't really need to worry about the fact that there won't be a fifth one.
From Karazhan we have the Illhoof heroic. Illhoof can only be hurt by killing his imps. When an imp dies it does 2 damage to him and comes back. On heroic these imps are 2/2s for 1 mana, and he even has spells in his deck that summon two imps for 2 mana.
So on your second turn you are often facing three 2/2 minions that respawn every time they are killed. This would be problematic even if Illhoof wasn't going to do anything else in the game, but his deck is half-filled with removal, so if you think you are going to stop those imps with taunt creatures you likely have another think coming. Even if you are killing every one of his imps every turn, he starts with more life than you, so the imp attacks will kill you before the imp deaths kill him.
The only solution I can think of is to get some imps of your own. If you steal an imp you get the unkillable creature and it still hurts Illhoof when it dies, not you. The mind control class is also the best silence class, which lets you remove his imps.
But even when you build the steal and silence deck there is a very good chance you will lose. Like I said, he'll often have six power on his first turn and spells that let you take control of his minions are random and expensive. I cast a number of Mind Control Techs while facing boards of two imps and two other minions and lost my coin flip. I got an absolutely shocking number of Demonfires from first turn Mind Visions.
If the encounter were tuned in such a way that you could easily recover from getting a useless card from your Mind Vision and then failing to take an imp with a Mind Control Tech, though, you wouldn't need Mind Control Tech. If he couldn't put you under so much pressure that you needed these things to go your way then there would be numerous strategies to win.
It's just like the WoW encounters that these fights are based off. Ignis the Furnace Master in Ulduar was supposed to be an encounter about carefully controlling his minions and exploding them away from the party and so on. It turned out that the easiest way to do the fight was to tank the minions and just kill Ignis before he beat you. Sartharion with three drakes was one of the hardest encounters ever designed in WoW at appropriate gear levels, but by the end of the expansion people were farming its special mount drops by simply burning down Sartharion. The difference between being able to do N dps and 0.9N dps (for some value of N) isn't winning 10% slower or faster, it's playing an entirely different game.
If Hearthstone Illhoof had 20 life instead of 40, you could try to race him with your taunt minions. If they had made the encounter harder by making the imps only do one damage to Illhoof instead of making them 2/2, you could live long enough to play more powerful minions and spells and open up new avenues.
I had to restart Illhoof a lot of times, but the time I won I simply crushed him. Sky used Kel'Thuzad and Moat Lurker to beat Malchezzar on heroic. On normal mode I used a 33 power C'Thun - he simply died on my first turn against him. On heroic you'd need that C'Thun to have 72 power, so it's a considerably less viable approach, and if you want to take it, you'll need to have a fair bit of luck to make it happen. There are a number of strategies that can be used to beat Malchezzar, but all of them are going to require restarting until you get the right combination of cards at the right time.
So I'm not sure I love challenge in Hearthstone heroics. Raid bosses required solving puzzles of what to do and when, and then executing your plans very well. Hearthstone bosses usually have a single puzzle to solve, and the rest isn't execution, it's just waiting for the dice to come up your way. I haven't found the puzzles hard. As for reshuffling, I guess I shouldn't disparage the skill it takes to actually do that until you win, but I finding it hard not to today.