I actually restarted yet again last night with the warrior on impossible. Holy cow, sooooo easy early on compared to the mage.
With the impossible mage gift pack restart, I just went straight to kiting every map except for tekron (honestly, I'm still not sure how I did it...).
With the impossible warrior, I just immediately cleared the first map, no kiting.
Either that, or I have played this game waaay too much.
Yeah, the paladin resurrection is QUITE appealing for a smooth game play, but I usually try to aim for no-losses anyway (just to get the medal ASAP). So far, it seems like having some rage for the next battle is really key. I'll find out soon enough though.