So don't fight them in a way that requires a saving throw. Stay out of range. Or avoid, run, or parlay....
Back to Perseus: He didn't survive against Medusa because he made his saving throw. He survived because he never had to make the saving throw roll in the first place.
It's not entirely random in the greater context of the game. Players have a say in what happens to their players, too, and IME are quite adept at keeping PCs alive against the odds. They have preparations, tactics, clues, and so on.
I'll grant that a DM of a Toleinesque campaign who says "You round the corner and see a medusa, so make your saves" could be being something of an ass. But in the Grotto of Gygaxian Gotchas, a lurking medusa is probably the norm, and the PCs should have a way to deal with it.
So, in the Dreaded D&D Dungeon you should know better than to touch anything, because experience teaches you to expect 0.37 deadly traps per room and your 1st level thief has only a 10% chance to detect/disarm any trap? The result is more like paranoia than suspense.
The Perseus/Medusa example doesn't work as an analogy, imho. As far as I know the story, Pallas Athene took action, gave Perseus the valuable shield and instructed him. That's not what I'd call "character ingenuity", it's railroading with the help of a powerful NPC.
I think we all want some method to increase suspense apart from the very lenient D&D system of whittling away HPs.
The SoD method works if the players know the rules governing the effect (petrification by looking at the monster, InstaDeath by a spell) and get hints about the threat so they can prepare their characters for it. Any error they make may result in character death(s).
This isn't the sort of suspense I like, if only because of the meta-game component: the players are forced to work on a meta-game level, they are playing some Dungeon Chess against the GM, not a roleplaying game.
For me, some system like the 4e Medusa works much better. As soon as one character falls victim to the monster's gaze, the pressure on the other characters - and thus the players - mount as they not only have to kill, chase away, or somehow get rid of the creature, they also have to save their comrade by quickly applying some effect to her.