In fact rewinding and mutation could both be used to kill an immortal creature.
If you make a creature immortal with a spell/ability, then it is rewinded and you play it again, it is once again mortal and can be killed. Logically though it is still the same creature (even if from games point of view it is a new creature).
With mutation it is similar - you change an immortal creature into a (probably) mortal creature and kill it, even though it is still the same creature.
I think if immortality is to be treated seriously, killing an immortal should not be possible any way, not just harder (if it was just harder we should call them 'hard to kill' not 'immortal'). The only way to deal with immortal creatures should be to stop them from attacking and/or using their abilities, or to kill their owner.
On the other hand I am pretty much sure adding a simple condition
if(creature.hp < 1) {
if(creature.immortal == true) {
creature.ableToAttack = false;
}
else {
creature.die();
}
}
(and a similar condition when a creature is healed/buffed to check if it can attack once again)
is much easier (and requires A LOT less maintenance and is much less prone to bugs)
than having a list of spells that can or cannot hit an immortal creature and having to decide with each new spell if it should affect immortals or not (imagine a spell with two effects like icebolt, should it be able to freeze but not damage a creature?, or just not possible to cast on immortal creature?)
On the other hand my solution solves it straight away (you can freeze and damage, just not kill).
On the other hand just add a few more statuses (like invisibility, ethereal, burrowed, probably more in the future), and for each you have to decide if a spell (or for example some permanents effect) can affect it... it is a lot more work and many more possibilities for programming bugs. Well, for some statuses it will be necessary, but I think for immortality it is not... (or in fact we only need to consider spells/abilities that can affect immortality like lobotomize/rewind/mutate, which is still much less than all damaging and instantly killing spells and abilities).
It's just an opinion though, and I don't know how it is really coded, so I might be wrong.
______
EDIT:
I wonder how instantly killing skills are coded...
I guess they might need a bit more work then I guessed at first, but right now they can see a difference between targetable and untargetable (right now immortal and burrowed) creatures just like any other skill, so it might need adding a distinction between abilities which will require some work, but Lanidrak's solution as well.
Anyway I am not an experienced game developer, and NOT an elements developer, so these are still wild guesses...
I have no experience with browser games, and my only experience with coding a game like this was making a deck builder in Java for a custom-made card game for an Objective Programming project
which is a much simpler work