I just finished Impossible.
To make it easy for myself I made sure I had Green Lantern, Lex Luthor, and Batman in the first 10. If all 3 weren't there I would just reload because if they were after the first 10 they would wreck me.
Using the same AI mind games that I posted earlier I was able to destroy Impossible once I had my 3 nemesiss out of the way. I had some trouble with Bane and Doomsday because they could lay on the damage quick, but even with that I was able to keep my health in the silver going into each match.
At the beginning of the match make sure you jump in with down + heavy, then heavy, heavy (JD+3, 33). That will net you a 23% combo and get you the "over 20% combo" health bonus. Then after you knock them down if you are on a stage with an interactible in the beginning jump up and throw it right way to earn "use an interactible" health bonus (if you are in the wayne manor stage work you way to the far right and throw the gargoyle).
If you find yourself near a stage transition, after you knock the opponent down do a meter burned back + heavy (B+3, MB). The AI will wake up with an attack and you will knock them for a loop.
I ONLY used my meter for meter burned back heavies, meter burned supernovas, and to win a clash. The rest of the time I just sat on full meter and continued to use jump down heavy, light light medium.
The computer is no where NEAR as block heavy as on The Max. Sure they will combo you up if you give them the chance, but they will almost constantly fall for the jump heavy technique.
Now I got the super easy Full House to do. I say easy only because I can use continues.