On Heroic she sends two minions back to your hand every turn and plays first a lot of small minions and later some bigger and dangerous ones.
What are some good strategies to use against her?
I was able to beat heroic Maexxna with a Hunter rushdown deck. As others have mentioned, your primary strategy is to make sure that her board is filled with 1/1s or 1/2s to lessen the damage you're taking each round.
The key to winning as a hunter, however, is not to outlast, but to outpace her damage. Unleash the Hounds will net you a ton of 1 cost 1/1 minions with charge (and you can throw in 2 of the neutral Boars as well), but the bigger advantage here, is that Maexxna tends to ignore them.
But even if you get out 7 hounds to her 7 spiders, you're still looking at a loss, due to her 15 HP advantage. To tip the odds further in your favor, consider:
Timber Wolf -- All your 1/1s are now 2/1s. Hope for this guy to get bounced back to your hand, because Maexxna does target this guy when possible.
Animal Companion -- You have a 66% chance of getting either a 3-cost 4/2 with charge (Huffer) or a 3-cost Timberwolf+ (Leoric). Misha is, unfortunately, pretty useless in this matchup.
Explosive Trap -- The perfect card to turn those 1/2 deathrattle spiders into 1/1 board-clogging spiders. Consider Also Explosive Shot if you're running into issues with the Sludge Belcher (Maexxna's only Taunt minion).
Weapon Cards -- Eaglehorn Bow and his big brother are pretty good damage, and won't get bounced by her hero power.
Kill Command -- Don't waste this on minions. Set that 5 damage (You do have a hound still, right?) straight to that Spider's face.
Houndmaster -- +2/+2 & taunt for a beast can give you a little bit of extra damage, with the caveat that you'll lose the minion if it doesn't get bounced. On the other hand, if your Houndmaster gets bounced, you can buff another minion, too!
Abusive Sergeant -- "Effectively" a 2/1 charge if you already have a charge minion on the board. For 1 cost, that's pretty good. And if he gets bounced, rinse and repeat!
After struggling to win with Freeze mage, I switched to this hunter strategy, and won the very next attempt (and that was even with forgetting to stick Timber Wolves in my deck!). As before, the RNG of Maexxna's draw means that it can't help to have a little luck in this fight. Don't give up, the RNG will eventually fall in your favor!
One very interesting approach is to play Priest with Lorewalker Cho and Shadowform. As soon as you can cast both, Maexxna will have a Shadowform in her hand and she will play it. Which basically turns her ability off.
Another way, which I have used myself, is to use Warrior with Voodoo Doctors, Earthen Ring Farseers and Charge Minions. The primary goal is to flood Maexxna's field with low-attack Minions, ideally 2 Nerubian Eggs and 5 1/x minions, although up to 7 1/x also work. To achieve this, you need some luck with the Minions she has and have to kill off the 1/2 spiders at the right time. Once her field is clogged up, ignore it, then a combo of Voodoo Doctors, Earthen Ring Farseers and your Hero ability (depending on what you draw) brings your life to either a constant value or even up. Make sure you never play more than 2 Minions. Using Weapons and Spells, you can then deplete her life while keeping yours up. Occasionally throw in a Charge Minion, but keep in mind your Minion total should not exceed 2, otherwise you might lose an important Minion that gets destroyed instead of bounced. If available, Captain Greenskin can make your Weapons last much longer. Once you have lethal, just play everything and swing for the win. Don't do that though unless you actually have lethal.
This strategy also works with Paladin (Guardian of Kings is very important here as your Hero power doesn't up your life by 2) or Priest (no access to Weapons there, though, which makes it somewhat harder).
The advantage of this strategy is that it requires nearly no cards from the Expert Set and is thus available to everyone.
It's pretty easy to engineer (with a board sweeper) a situation where Maexnna has 7 1/1 minions on the board, i.e. is attacking you for 7 a turn, and has no space to bring new, stronger minions into play.
In your hand at this stage you'll want: Guardian of Kings, Earthen Ring Farseer, Wolfrider.
Once you have 10 mana, cast Guardian and Wolfrider every turn - Maexnna loses 3 life per turn to your (in aggregate) 1. If you're close to death cast Guardian and Farseer for a few turns instead to give you an aggregate +2 life a turn and bring you out of the danger zone.
The trick is quite simple once you get the hang of it.
What you need to do is mitigate the damage until you can reach late game (having Alexstrasza for the late game kill will make this very easy).
Keys to the deck:
Some decks you can consider is a old school zoo hunter deck with UTH. Just keep a hard removal or two handy in case she squeezes out a Sea Giant.
I used a Priest. It's a good deck if you don't have any legendaries.
Must have cards:
Keep in mind you are going to go, more than likely, into fatigue. So once she starts to run out of cards, just make sure you will always have an answer for a sea giant or spectral knight on the board.
The most common ways is to play zoo(Suggest decklist: http://www.hearthpwn.com/decks/35326-budget-reynads-zoo-v2-warlock-aggro), flood the board with your minions ,make her ability less impactful, and zoo doesn't require epic/legendaries, it's generally pretty easy to make one for beginners.
If you don't want to play zoo, this thread might give you some inspiration: http://www.reddit.com/r/hearthstone/comments/2bhwmr/beating_naxx_heroic_w_budget_decks/
If you have Alexstrasza, there is a creative way to beat Maexxna :
I did it with Jaina,
elven archer, voodoo doctor,armor secret, and of course, antonidas
then every spells you need to clear the board.
he went out of cards and died. (Some luck needed to win this, i had 3 hp at the end!)
I used a priest deck and a combination of battlecries and charges. Basically, as others say, you want to flood her board with 1-X minions or even better if she uses the 0-2 nerubian egg to minimize the damange taken, ideally to 5, 6 or 7 per round.
Then, use your hero power and battlecry heals to sustain and charges to deal damage.
Unlike others, I think keeping only two units on the board is the key because you are ensured that they are returned to your hand at the beginning of the next round thus cycling the combo infinitely.
Pretty good combo is for instance Earthenring farseer + Arcane golem/Leeroy Jenkins + your hero power. That way you take 1 or 2 damage per round while dealing 4 or 6 damage.
I believe you can also play this with a warrior as in this case the hero powers are equal.
I just managed it with a basic deck, took me 1 day over about 4 hrs. Im really chuffed so i thought id help out u guys if ur having trouble. I must warn you tho, it isnt easy and it isnt fun. It requires PRIEST and a set routine for the start.
Basically maexxna must spawn deathrattle spiders and the plan is by turn 5 or 6 you use a spell to deal 2 damage them thus creating 1/1 replacements.
now ur gonna need a little luck and a few restarts to achieve this but its fairly easy.
so what do you do between turn 1 and 5? well make sure you have these cards in ur hand or 90% of them so to speak, at the beginning. read on for details. Stage 1. Plan for the HOLY NOVA by turn 5 or 6, in the mean time having VOODOO DR and ELVEN ARCHER are v.good starts, if you can get a 1/1 charge also it gets the ball rolling on lowering her health slowly.
I say slowly because ur gonna take this b***h out in one hit eventually, and ur gonna have to be very smart and tactful to do it.
So dont charge the minions at all, let the HOLY NOVA do that job.
for example she will ideally spawn 4 spiders thus creating 8 1/1's after deathrattle and jam the board. The board only takes 7 anyway but lets say she had another minion out there before the deathrattle, ur gonna have to deal with that first in THE SAME TURN as ur HOLY NOVA otherwise ur defeating the object of the tactic. Thats why i say turn 5 or 6. i recommend the HOLY SMITE card first on for example a 4/4 minion at cost of 1 mana and then HOLY NOVA to take them all out. Of course i said it was hard, and it is, to get this opening AND having these cards requires a little luck but not impossible.
She will have ur health down to mid teens by this point so stage 2 is all about health.. heal urself as much as possible as shes gonna be taking 7 hits off you per turn.
Ull need PRIESTESS OF ELUNE, VOODOO DR and EARTHEN RING FARSEER. but YOU MUST NOT use all 3 together, the most important rule is 2 MINIONS ON THE BOARD AT THE END OF UR TURN. if your serious about this tactic ull have to be patient.
Just to recap, ur goal is to allow her 7 hits per turn, heal urself and wait for the right cards to come along to finish her.
what are the cards? well its easy.. CHARGE...
anything other than a charge wont work, its got to be done in 1 turn when all ur cards have come together - 2-5 charge (stormwind knight) 2x power word shield and 2x devine spirit and inner fire. = 27 attack.
its not that impressive, and it doesnt have to be. I managed with a 14 hit to kill her but plan for it anyway. even having a ABUSIVE SERGEANT is a must.
Why is it a must.... well
Stage 3.. final stage..
most of the cards are unwanted.. u have to pick 30 anyway and this isnt good for you in this deck. ull have cards coming out and you wont be able to use them... uve got to keep ur health up and can rarly deviate. so what happens if u need a card and ur hand is full.. well, uve got to sort it out! this deck is full of spells but u will still have minion cards in your deck that u dont want and are blocking you.
this is the fun part.. be tactful, ull find a way around it.
I managed to beat heroic Maexxna with a modified freeze mage.
The key cards to the deck are:
Other cards that can clear the board or deal direct damage are useful but not required depending on your preference. I also included 2 Arcance Missiles and 2 Arcane Explosions but they are probably not required, or even advisable as it is better for their board to be full of 1/1's than other potentially dangerous minions.
The method behind this deck is as follows:
The draw backs:
I managed to beat heroic Maexxna on my third try with this deck. Bearing in mind I didn't have any Ice Blocks, in maybe both of the losses it was very possible that I could have won with those extra turns. The main thing that kills this deck is fatigue. You almost always draw into your healers early, meaning you can heal yourself up every turn, plus the frost nova, big board clear in the form of flamestrike and blizzards means the game can last a while. The game kind of boils down to using an argent commander to smack in the face and then an earthern ring farseer to heal. It's slow and may sound a little tedious, but it's effective.
I used a strategy similar to what ChaseC suggested (I didn't use Mind Control tech though). No matter what class you use, 2*Voodoo Doctor and 2*Earthen Ring Farseers are critical.
Now that more wings are out, Loatheb could also be a great addition to the deck.