As before with the Blackrock Mountain thread, I think it helps if we post the decks we used to combat the bosses on Heroic in this expansion. I'll update this as I beat them, only had time to beat the first one now. Will update later as I beat the others.

Wing 1

Zinaar

Pretty straightforward counter against his hero power. As always with heroic, you require some luck of the draw to be succesful. Took me 3 attempts with this deck. Try to mulligan for Mana Wyrm as he often ignores it for a couple of turns when it can get insane damage in. Fun fact, in all three matches I didn't draw a single Flamewaker once. If you do, that ought to do some serious damage too. You can scrap something for a second Ice Block, I only had the one.

In the end, you'll basically want to burst him down. Either with Mana Wyrm value, Flamewaker value, Violet Teacher value or Antonidas value. You can try putting Illidan in for some fun, but I think he costs too much in this matchup to be worthwhile.

Phaerix

Again, pretty straightforward. Silence the staff, destroy it. If it takes too long to draw a silence, just use Pain instead and silence it later. Of course, the traditional combo wombo works very well here (Lightspawn, Shield, Velen's Chosen, Divine Spirit) as I haven't seen him use any hard removal. He's also a complete idiot about attacking with minions you cast Glory on. You'll heal 4-8 each turn pretty reliably. I got the win first try with this deck, but I got pretty lucky with a silence draw relatively early on and got the combo wombo at just the right time.

Temple Escape

I was surprised how easy this one was. I didn't get that great of a hand and made it out with full health and 8 armor. It helps that he kills his own stuff on turn 5 or so, and Illuminator was actually really great here. I have no idea if Mirror Entity works, I didn't get a chance to try it. I'm sort of assuming it won't, so in that case you might want to replace it with Big Game Hunter.

Of course, general strategy is to not have a board presence at all because they get wiped on turn 5 and the boulder murders them. Instead, just stall for 10 turns (or in my case 9 since a 7/7 is no real threat with this deck). Use the various freezing effects to stall. Vaporize is exceptionally good and Polymorph, Flame Lance are very strong too since he exclusively plays big threats. Made it on the first try with this.

For the second heroic boss,you just need to gain board control with alot of taunts like Deathlord. Then you shave to silence the staff and destroy. After that he can't become immune again. I also hear there is an exploit where if you silence the staff and then steal it. the boss won't know what to do after you put it behind a taunt.

Deck I used: http://www.hearthpwn.com/decks/366667-heroic-sun-raider-phaerix

For the third boss, you can just use a standard freeze mage with some tweaks. Stall with cards like mirror image and annoytron until turn 5. Then you apply lots of freeze to get you to turn 9. This is where a turn 10 ice block will win you the game.