Yep, I didn't realize there had been a discussion about this before.
Your suggestion makes a lot of sense, but in practice I'm not so keen on it. Take this for example,
An Otyugh devours an Immortal creature, that Otyugh gains +1/+1 and the creature is returned to your hand? Obviously you would want to play that creature again, but that will just eat up your Quanta and make the enemies Otyugh stronger.
Another example, your immortal creature is a 5/1, making it the perfect target for paradox. All your opponent needs in play is a Maxwell's Demon or a mutation with Paradox, again, you would lose your immortal card every time you played it - and generally speaking, putting a creature into play costs more than certain abilities to remove creatures: 'Devour' and 'Paradox' being the two most obvious.
My suggestion is slightly different:
Immortal: Immune to damaging effects*.
Ethereal: Cannot be targetted.
*Damaging effects include: Firebolt, Icebolt, Drain Life, Paradox, Chaos Seed, Aflatoxin, Poison, Infection, Gravity Pull, Devour, Rage Potion, Rain of Fire, Fire Shield, Inflate, Holy Light, Thunderstorm, Owl/Eagle Eyes Attack and Lightning.
Every other effect in the game, will still apply to Immortal creatures. The alternative will be to give Immortal creatures infinite hit points, therefore making it impossible to remove them from the game through damage effects, but then, this would lead to the obvious abuse of Gravity Pull etc....
Ethereal creatures simply cannot be targeted, now I'm not sure if this should leave them open to damage from global effects? Such as Rain of Fire which does not specifically target something - another example would be Animate Weapon on the already immaterial Morning Glory weapon. Or whether Ethereal creatures should work like the immortality in the game already, completely immune to anything and everything.
