Heck, a "House Rule" can fix most of the problem really quickly:
If a creature has a Disintegration or Death Effect ability, remove that ability. Give the creature Haste, Displacement, and Dimension Door as spell-like abilities to compensate, or DR 5-10/-, or +8 to Constitution. Voila. A monster that survives quite a bit longer, has the ability to run away, and is a tad harder to damage.
Do this only for monsters where the death effect seems tacked on. A basilisk and a bodak are otherwise weak monsters with a limited instakill power -- it has a limited range and a fairly easy save.
But a beholder with self-hasting, DR 8/-, Regeneration 5, a Dispel Magic eye ray, and Dimension door usable 3/day, in the place of, say, Death Spell, and Disintegrate, is going to create a much longer and more involved combat. He's still got the Hold and Flesh to Stone stuff going on, but a high level party can get past those problems quickly. He's dangerous, but he probably won't kill as many people -- although he could still finish off an unprepared party fairly easily.
Or, as another option, items. Several of my players have items that stop Death magic aimed their way. The items have limited charges, and take up an item slot. They have to choose whether to wear the "no death spell" amulet or the "+2 Dexterity, Fire resistance 15" amulet or the "+3 to Fortitude Saves" amulet. If they get killed by a beholder because they wore the wrong amulet, that wasn't horrible game balance. That was strategy, and a choice on their part.
-Tacky