Save-or-die effects are not necessarily in and of themselves unacceptable. The problem has to do with how they are applied and how often. If you're going to reduce a characters entire fate down to one RANDOM die roll then you better be sure that having arrived at that fateful moment hasn't been an uncontrolled crapshoot. If PC's know they're going after, say, a Medusa then they accept that there is the threat of such random death and should be able to mitigate the dangers to some degree. There are a number of ways you can do that.
With, say, protective spells a medusa gaze might not be save-or-die but instead require three failed saves with graduated debilitations for each. With appropriate tactics the chance of failing the single save might be greatly reduced. With costly but readily manufactured cures those having been stoned can be re-animated.
Save-or-die attacks should not all be lumped into one category, one-size-fits-all methods of being handled. One such attack might require protective spells, another protective equipment, another appropriate tactics, and still another simply require curing or reversing after the fact. Insisting that they should all be handled just ONE way would be a stupid approach that abandons the possibility of making the game and certain spells and monsters more interesting in favor of the vastly over-valued "universal" mechanic.
And, of course, sometimes a characters luck should run out and they should finally and permanently die. It just shouldn't be from a random save roll brought on by a lucky attack made by a wandering monster that was just being used as filler before the party actually reaches the dungeon. Permanent character death MUST be a part of the game. Pretty much by definition that means it is an event that is out of the players hands to always prevent. It is similarly not always in the DM's control to prevent it.
Traditionally I have simply reminded my players as their DM that characters WILL die and it won't be because I'm trying to kill them, but because I must maintain the possibility of their deaths or else what's the point in even running combat? Then I try to be particularly judicious about what save-or-die monsters and spells I throw at them and how they come to be facing them. However, I think FAR greater strides can be made with mechanical changes than what has been done thus far with existing editions.