Hearthpwn

The theme of this deck is pretty simple and shows up in its name - being stubborn. Survive and outcontrol Maexxna until she runs out of cards and you have full board of stuff every turn.

Why you chose paladin and didn't include Holy Light, you stupid...

Well, I did not include healing via spells, because I thought with Maexxna's overwhelming board control (she has two 2-mana minions from start! hax!) it really wouldn't matter and I wasn't that desperate with my deck. My strategy against the Spider Queen is playing cheap minions with Charge or cool Battlecries + squeezing huge value of your mass-removal. And Paladin has both - my favorite Argent Protector and second favorite, may not be so good here, but nevertheless, Aldor Peacekeeper (follow the rules, yo) + glorious Consecration.

The deck-list is tentative and exactly the same as I've beaten the boss with, and may get more thought into it. And that is why imba-card Mind Control Tech is not included here. I thought of it right after I've beaten Maexxna, but you should do it right now! Also you may think to get rid of one or both Stampeding Kodos, but they played for me just nice.

The THING to remember: boss always uses her hero power, Web Wrap, first on her turn, and it should be used for our advantage. In Heroic mode, this hero power costs 0 mana and removes TWO of your minions back to your hand.

Considering that, the key-card in this match-up is... Voodoo Doctor. This brave guy, for whom you always should call, will serve you very well, if you draw him in your starting hand. Also, of course, you always should keep Consecration. The other good cards for early are Bluegill Warrior in conjunction with Argent Protector, Ironbeak Owl to knock down deathrattles, and Earthen Ring Farseer, as more healing, duuh. Elven Archers and Argent Squires are fillers.

Another questionable, but still-seems-nice-to-me thing is to combo weaponry with Southsea Deckhand. Big Game Hunter is a must-have, in my opinion, because Maexxna just loves Sea Giants so much and has at least two (NOT APPROVED BY KEL'THUZAD). With good fortune, you can kill every one of them with the same BGH!

If you have any questions/suggestions/angry reviews, please, write them down in the comments (that's my first guide anyway). GLHF!