For me, the problems are threefold.
Firstly, there's the lethality aspect. They make it very easy to kill a character, which then either means hours sitting out of the game (creating a new character and having him written in, or a lengthy quest for resurrection), or they require that the game has easy resurrection, which I detest.
Secondly, they're just too damn swingy. It doesn't matter how well you were playing your character; lose initiative, miss a saving throw, and you're done.
Finally, on the caster's side, they tend to be very much all-or-nothing. The evil Wizard enters combat, cackles evilly, launches his most devastating death spell... and all the PCs make their saves, and come through with no effect. And in the worst case, that may prove to be the only attack that the Wizard gets to make before he gets minced.
So I think I'm leaning towards a model where SoDs become "if you hit you get a lesser effect; on a critical it becomes SoD" as my preference. That way, they're much less immediately lethal (since a true SoD becomes much more rare, while still being a real risk), they require two rolls to kill a character (or, even better, three if criticals require confirmation), and they cease to be all-or-nothing effects.
(Plus, that also has a nice symmetry with my notion that a Fighter, on a critical hit, could choose to forgo the extra damage and instead disarm/sunder.)