My Maexx heroic strategy is probably more luck based, but it worked.
I just made a Hunter to the face deck. Drop Bluegill/Wolfrider/Leeroy each turn to burn the face since they get bounced anyways. Use Freezing Trap to bounce the larger minions, AI is dumb enough to attack with the largest creature first. Your goal is to get 7 weak creatures on their side of the board so that they can't play any good creatures. One turn before I was going to die, I dropped 2 Timbers, Unleash, Explosive Trap and hit for 15. Maexx triggers Explosive, I live one more turn to finish off with Leeroy. You do have to get lucky though - you have to draw some kind of Unleash combo fast, and have your Explosives