So, if you play Quintessence on a creature - it would work exactly like Immortality currently does - the creature is immune to anything and everything.
The question remains if shields (especially fire shields) should affect ethereal creatures. (In my opinion they should, because it is not targeted, and ethereal creatures need to become material to attack).
Thus ethereal creatures can be killed in two ways - either by shields, or if they were poisoned before becoming ethereal. Immortal creatures on the other hand should not be able to die from poison or shields (although other shield effects would still work on them), even if you poison an immortal before it becomes immortal.
or as you put it, mutate the creature into the same version of itself without immortality.
I meant something a little different. I'll give an example.
Take Superman, and assume he is immortal. No amount of punishment can kill him
(Kryptonite would be that 'card removing immortality' that some people required, although I do not think such a card should exist).
Now, lets take our Superman into Chernobyl, or some nuclear testing ground... and expose him to extreme amounts of radiation...
Now if he was able to mutate into some other creature due to radiation, it would be the same person, just in different shape and form... for example a two headed cow from Fallout universe
The question is, should this cow, which is in fact Superman, be still immortal?
And my answer is - Superman would just not mutate. He is immune to mutation, because he is immortal. And even if he mutated, he would become a Supercow =D (still immortal).
And I think icebolt has a 30% chance to freeze, just like the shield. And if you (for unknown reasons) include an icebolt in a rainbow deck, or eg. a trio deck, then it would be less of a damaging spell, and more of a creature control spell. Also I've seen fake gods and AI3 often using icebolt even if it would not kill the creature, although often freezing it. Though, chaos seeds and freeze/congeal were more reliable in this case.
I think that cards such as chaos seed and ice bolt should be able to target immortals, you would just apply only the effects that cannot kill (either 'rerolling' the random choice, until an effect that can target immortals is chosen, or the spell would just fail if the wrong effect is rolled).