Immortality is no problem on the creatures that are designed for it from the beginning (i.e. Phase Dragon). I consider them quite balanced. It is a problem with the quintessenced Otyugh/Druid/... . Now if the game would remember which status effects are additional to the innate abilities of the creature a card as the Dispel described here (
http://elementscommunity.org/forum/index.php/topic,2039.0.html) would be possible and provide a solution.
It probably would mean a redesign with the card handling and fix some of the bugs that come from multiple status effects on each card.