Averting your eyes gives a 20% miss chance. That means the fight is going to last longer and you cannot target targets by sight (negating a number of spells). It also only works 1/2 the time. Sure, it messes with the chances, but, in any case, it's still much higher than 0. 5 CR 8 creatures shouldn't even register against 20th level PC's. Yet, here we've got a chance of a PC death that's still significant.
((No, I can't do the exact math.

))
Note that with gaze attacks, you make a save on your turn, so long as you are within range. Put 5 bodaks into a 20x20 room. There, everyone makes a saving throw. With an extra 5 saving throws on the bodak's turn as well. Having an encounter that starts at 30 feet isn't terribly unusual.
What specific parameters does a gaze weapon have before it works. From the srd:
Each character within range of a gaze attack must attempt a saving throw (which can be a Fortitude or Will save) each round at the beginning of his turn.
There's nothing difficult about it. If you start your turn within 30 feet of a gaze attack creature, you make your save(s). Plus the forced save on the creature's turn (although that only affects one target).
I do agree with you that SoD spells are different creature. Usually, they only affect one target. That's lethal, but, not totally out of the ballpark. I'd much prefer a slower effect though. Get tapped with Finger of Death and you gradually weaken until, X hours (days/weeks whatever) you die unless you get saved in the meantime.
The problem with this, is spells like this don't work for players. Opponents aren't going to survive encounters (usually) so effects that don't come into play until several hours later are totally wasted. A flesh to stone effect that requires time is great for monsters, but pretty much useless for players.
I'd much rather just chuck the whole bag entirely. It's far too lethal to the PC's and doesn't really add anything to the game that you couldn't do in any number of other ways.