Phew, that took some doing. I just managed to defeat Maexxna on heroic difficulty, using a paladin deck I made for her. At first, she's incredibly difficult to handle, because her heroic hero ability returns 2 minions to your hand for ZERO mana, and she floods the board with deathrattle spawning spiders working up to mountain giants and evil taunters.
This is the deck I used:
Because her hero ability costs zero mana, the AI uses it at the start of every turn. So, I focused on minions with battlecries, charge, and other immediate effects. An owl can silence enemies multiple times, charging minions can charge over and over again, and earthen ring farseers (and later guardians of kings) keep you going. Humility and aldor peacekeeper keep the big minions from hurting you. Your goal is to use her multiple spawns to quickly flood her side of the board with 1 attack minions, keeping her from being able to play any more. Leeroy is good for this, but I didn't draw him during my match. Mind control tech can help you survive the beginning, but in the end, she had a ton of spiders, a 1 attack mountain giant, and I just kept playing Guardian of Kings and Wolf Rider until she died.