The beauty of the hp threshold system is that it's easy to adjust. If you want save or die to occur more often, raise the threshold. If you want a save every round or with every hit, make the threshold some ridiculously high number.
Behold the modularity inherent in the system! When presented with a dial, why not just be happy that you can set it to what you want instead of complaining that it can be adjusted to a setting you don't want?
Exactly. Having a good lever to move the system one way or the other is what is crucially missing from traditional SoD. The only lever you have with traditional SoD is to adjust the roll itself--thus the proliferation of bonuses to saves in AD&D through 3E. But at some point, that simply removes the danger to a 5%, auto fail on a 1. It's important for them to get the numbers close to right, but it is more important to have the lever in the first place. If you don't like medusas in such a system, you can always adjust the threshold or remove it altogether.
People objecting to it on contrary grounds for that point in particular are really stating that they don't want to be bothered to do even that minimal work--or that they want the "official" version to back them up when they decide to be use the harder options. Heck, it would be easy to include in the mechanics two or three stages of lethalness. Once the lever is in place, we are only talking a single number for a threshold. You could just as easily include three number, with the most lethal one often replaced with a "-" for "Sorry Charlie, you're dead."

Pick your column univerally or by monster, and off you go.
I think this is a good and useful mechanic, but beware of Hammer-Dependent Nail Observation Syndrome. In the context of the medusa, I strongly dislike it. It makes no sense to me that a medusa's petrifying visage only works on low-level characters or those who've been through a fight. Why is it that a high-level fighter can look a medusa in the eye with impunity? Or if it's some kind of abstraction where the fighter isn't actually looking the medusa in the eye, what exactly is the fighter doing? It gets way too metagamey, way too fast.
That's an easy one too. For effects nasty enough to have this objection, when the threshold is not met, the attack does hit point damage. The hero
can look her straight in the eye if he wants. Then he has abandoned his threshold and gets to attempt the save like everyone else. Or he can lose the required hit points in order to not need to even try the save.
Of course, once you go there, you might choose not to have the threshold at all, so that you don't have to worry about tracking them. Instead you have a "HP amount required to avoid a Save" -- or "Heroic Avoidance" cost. For any SoD, pay the HA cost or attempt the save. If the medusa's HA is 25, then anyone with 25 or less hit points is kind of stuck.
(The HA method doesn't have quite the range of flexibility of the threshold system, but if you want to build a penalty in for avoided attacks, it might be worth the trade to keep from worrying about when people hit thresholds or healers trying so hard to avoid them.)
If it were up to me, I'd go with the HA method for most such effects, and then tack on the previously suggested requirement of Death Saves (three strikes and you are out) as a rider on the really nasty ones. That's simple, and the rider on top of hit point damage is not something that will be easily ignored.