I thought the problem with save-or-die is that it's random and that it needs only one step, rather than because it kills without lowering HP to zero.
Actually, I kind of object to "one step" part.
A lot can happen between enemy starting to cast and instakill occuring. If the spell requires line of sight, you can move behind something or break line of sight using stuff like invisibility or some summoned cover/concealment (well implemented LoS requiring spell should check for LoS at the moment of casting as well). You can cast counterspell. You can inflict damage to enemy caster, physically or magically, to break their concentration. Stoneskin is bullshit, BTW. Even kicking stoneskinned mage in the ass or pushing him should have good chance of interrupting casting because it would interfere with precise, minute gestures required for casting. Any attack that *can* physically hit the mage (not just hit, can - you don't just miss in melee without target taking defensive actions) should have good chance of disrupting casting. Unless mage made themsleves ethereal or you can't get to them (due to mundane reasons or bubble-shield like spells) hitting them, even for no damage, should disrupt casting. You can try disabling mage physically or magically without attempting to deal damage - I'd assume it's hard to keep casting when someone grapples you, and no, stoneskin doesn't boost your STR.
Even in games where instakill is actually one-step action it's often preventable without metagaming - see Wizardry 8 - it usually doesn't take much genius to recognize casters at distance *before* combat starts. At the very least instakill can serve dual purpose of being effective gating mechanism combined with resource management when used by enemy (oops, powerful casters - no protections? - retreat) and valid crowd killers when used by the player.
Then, apart from casting delays you can have other kinds of delayed save-or-die attacks and spells. Maybe cloudkill isn't potent enough to kill you via skin or mucus membranes and requires to be actually inhaled to end you - then if you hold your breath you have limited time to act while already in the cloud (you can connect it with less rigorous than usual save mechanics - for example you only get this extra time if you have fairly intelligent/wise party member or NPC with you who isn't blinded or muted, or are intelligent yourself). Maybe area on which enemy cast Horrid Bolt of Doom and Utter Anihilation will start glowing and emit weird phenomena before the actual bolt plummets from the skies and turns it into white glowing molten crater?
Then you have already mentioned situational instakills - pinned enemy, backstab and so on.
Deterministic insta-killing? Interesting idea.
Why not? RPG isn't meant to be slot machine, probabilistic mechanics is there to add uncertainty, not to base whole game on. This means that deterministic mechanics is very well suited for at least prototyping the barebones mechanics, before you add skill and stat rolls, and all the other random stuff to force more robust planning and actual character building.
Traditional games (like chess) often had deterministic instakilling, and don't forget that HPs themselves started out as probabilistic survival buffer (before they went horribly wrong with level up inflation). You weren't guaranteed to survive if your 1d6 thief was stabbed by 1d4 dagger.
So, yeah, I would risk saying that:
1. You can have interesting deterministic instakill.
2. If your save-or-die mechanics is broken when you remove the save part, then it's broken, period.
3. If deterministic instakill works well as mechanics it will also work well when coupled with non-deterministic saves.
