Wow that was a lot of crap to get through before hitting the meat and potatoes...
I might have missed something, but where did the idea that the heroes cards would be untargetable? If that were the case then part of Immortal King's abilities would be pretty moot, and all the cards would be overpowered.
As things stand, I do think the only ridiculously over-powered card is Immortal King....But...
If I understand the quest system for fighting this series of NPCs, then it would be understandable that by the time you were ready to take them on, you'd be able to custom make an upped deck to be specific to that deck. Immortal King wouldn't be able to target creatures that were burrowed, or immortal themselves. Ja?
I had mentioned this in the chat room a while back but...
There used to be a ccg for Highlander: The Gathering (Don't laugh at me!)
In this particular game, you had pre-game cards. Some cards would be persona cards which would give you special abilities, some cards would represent personas that you've beaten and taken their power via "The Quickening".
Maybe in addition to Hero cards, there could be pre-game cards. OR....
Instead of having an element mark, have the Hero Card be your element, complete with powers. (Definitely have to redo Immortal Kings ability) But for instance, Death's persona poisons every creature on the board that isn't death or darkness, but you are poisoned each turn as well. Darkness allows the transformation and control of enemy creatures, but takes double damage from Light cards.
Well....You get the idea...
Which reminds me. There has been a lot of outcry to be able to upgrade your mark as the False Gods have. Maybe that could be one of the pre-game abilities....