Via Twitter: My DM, @trollsmyth, regularly demonstrates the principle that the only DMs who kill PCs are the ones who can't think of anything more evil.
There's been discussion in the past using monsters that are nastier than the levels of the PCs would indicate is “fair.” Yes, this sort of challenge really pushes your players to be creative and flexible. It doesn't, however, always go well for the PCs.
Last night, it was a water naga from the 1e Monster Manual. The AC of 5 is hardly anything to get excited about, and the 8 HD is nasty, but a large enough group can use the power of iteration to really pound such a creature into submission. No, what's really nasty about the naga is her ability to cast magic-user spells: “4—1st, 2—2nd, 2—3rd”.
The party decided to hole up inside the dungeon. They thought they were in a safer part and posted guards. (This is not as foolish a decision as it might appear on the face of it. Camping outside the dungeon could potentially have resulted in being ambushed by something far worse than the naga.) The naga, having discovered where they were and knowing they were after the treasure she was guarding, cast invisibility on herself in an attempt to sneak up on them. It was only partially successful; one of the guards overheard her slithering up and woke some of the others. Not that it mattered too much. When the naga was close enough, she dropped her invisibility and launched a nasty alpha strike. The sleep spell took down all but one character, and that was a cleric who didn't last very long after that.
While I'm certainly not suggesting that PCs should never die, too frequent death removes the sting as much as any invulnerability; when death merely means a quick, fifteen minutes rolling up a new character and dropping them into the dungeon to get back into the game, what, then, really is the sting of death? The loss of stats, and maybe some equipment? When players expect to lose a character, they avoid investing anything emotionally. Then they truly do care more about the magic sword or ring than they do about the person wielding it, because the magical trinkets are the only things that truly last. (And while that can actually make for a very interesting theme to an Old School game, it's not the sort of thing we're aiming for in the current games I'm running.)
However, if you're up to playing a bit by the seat of your pants, and have a nice, open, sandboxy-type campaign, player defeat just means a bit shifting of the gears. In our case, the naga now had a nearly intact adventuring party at her disposal. By keeping a few of the NPC hirelings as hostages (and being prepared to indulge in the liberal use of the charm person spell), the naga was able to convince the group to perform a “small service” for her. It's a tangent, a side-quest that might grow into something greater.
What will the future hold? Will the heroes grudgingly accept the naga as an ally to their cause? Or will she become a hated foe, a nemesis to be hated and hunted a few more levels down the road? I don't know, which is part of what makes this sort of thing as much (if not more) fun for me than for my players.