I think the main problem with immortal is it's redundancy in comparison with the other on element cards.
Phase Dragon and Immortal offer almost exactly the same metagame position, of the immaterial beatstick. With the only difference being the attack power, Phase Dragon is clearly stronger at what it does.
Phase Spider and Immortal both offer another similar metagame position, the mid-range attacker. But in this case the spider completely outshines Immortal because of it's cost ratio.
It's even overshadowed by Aether Nymph, which is a much better attacker for it's cost, and has the ability to immortalize others.
Heck, even Ball Lightning outshines Immortal, it's free and does the same damage, albeit for only one turn, and can be fractaled to produce devastating results.
Immortal is currently filling a metagame niche that is totally redundant within it's element.
Without some kind of severe change, it will continue to be UP no matter what you do to it.