Players don't want their characters to die either. Should that be removed? They don't particularly like getting hit, remove that as well?
True, no one wants their character to die. But, it's a far, far cry from "I don't want my character to die in a totally arbitrary way that I have no control over" and "I don't want my character to get smooshed by repeated hits from trolls."
Everyone keeps focusing on the medusa. but, in AD&D, there are a whole host of creatures that force save or die. Many of which are not things you can automatically prepare for. Snakes and spiders come to mind right away. It's not unreasonable for a PC to be surprised by either one - not all spiders spin webs and snakes are kinda known for that whole surprise ambush thing.
I lost far more PC's to snakes and spiders than combat damage in AD&D.
It's not about adventuring with rubber rooms. It's that it's entirely arbitrary. Either you have the counter, or someone dies. Listen at doors? Sure, I hear a woman talking. I should automatically assume medusa? Wow, metagame much? I see small birdlike tracks. I should automatically presume cockatrice? Depending on the track roll (and depending on the edition - after all, without a ranger, I cannot detect tracks AT ALL in AD&D) how do I tell the difference between cockatrice and kobold tracks?
Never minding why there are tracks being left on stone floors, but, hey, we'll ignore that for a minute.
Or a banshee? In Land Beyond the Magic Mirror, there is a banshee in one location. There are no clues that she is there. None. You walk in and whammo, instant death saves. In one of the Dragonlance modules (the exact number escapes me at the moment) banshees are a random encounter. An arbitrary roll of encounter distance + initiative roll can lead to the banshees getting the drop on me and having zero opportunity to prepare.
In A1, there is a basilisk as a random encounter - how do I prepare for that?
In the Savage Tide AP, 5 bodak assassins riding undead tyrannosaurs teleport out on top of the party at a random point - no warning.
And this is perfectly in keeping with D&D actually. Bodaks ARE demonic assassins. It's one of their reasons for being.
Retrievers also have SoD abilities. Their entire purpose is to go out and hunt specific people.
The idea that SoD creatures should only be used in very specific circumstances where the PC's have ample opportunity to prepare themselves isn't supported by the rules. Quite the opposite in fact. SoD creatures are meant to be used as Aha Gotcha monsters when the players are least prepared. Whether it's monsters like Rot Grubs and Green Slime or intelligent stuff, older versions of the game were chockablock with this sort of thing.
If that's the kind of game you enjoy, more power to you. I do not. I find them arbitrary, far, far too metagamey, and lead the players into a very antagonistic relationship with the DM.