I think DM spice is best complemented with PC decision. In OOC discussion with another player, I heard that they were given one of two options, with consequences for each. That gives players a feeling of fairness and justification when things pan out one way or another.
Some quick examples that I liked:
Early in my career, my mid-level F/C was taking a group of newbs through Mary's quest. On the way out, several Chosen appeared and our magic weapon spells were wearing off. After holding off the Chosen for a while and listening to their DM interjected comments, it became apparent that no one could really harm the monsters and my character took the initiative and called for a retreat. The newbs wisely followed my character's lead, and everyone survived what was quickly turning into a disaster. I got my first DM XP for that, and it was quite a thrill.
It was a simple, non-plot intensive bit of spice, but that as much as anything hooked me on EfU. Immersion was MANY times more effective and it was huge fun.
Recently a high level barbarian challenged the Stoutheart Clan to offer a champion a duel for the right to meet in the Arena. After he whomped our 9th level fighter soundly - which was obviously the DMs intent - we were a bit humbled but no one died and the RP was quite memorable on both the DMs and our part.
I'm not going to comment on the negative things I've heard, but in each case it appears that if the players had been given subtle or even obvious indication that they were about to take some very high risks, that they wouldn't have minded character death so much.
This is just a suggestion, but if the DM can give clues/hints that the players may be biting off more than they can chew, then it's only the players' fault if their 6th level pally attacks the Balor that just threatened to destroy their party if they didn't leave immediately.
It's an extreme example, but it appears that players are the most bitter when they feel like they had no RP way to avoid death other than to imbibe a INVIS potion and run like a little girl.
If you are playing a proud, fearless fighter that hates magic and potions, being surrounded by DM placed Troll Beserkers on the way out of a dungeon after a quest will seem like the DMs have decided to waste your character. Again, if that 8th level dwarf barbarian has some other way to survive than drinking an invis potion, it will make for some great RP. Maybe a Troll Beserker's female mate runs up and cries, "Stop this fighting Grok! Don't you see that fighting these small ones is wiping our people out?"
The trolls pause, and the dwarf has an opportunity to RP his way out now. Back up slowly, bribe them, whatever. If the player decides that Ungrimm the Stupid will smash Grok in the back of the head when he turns and will likely go down under a swarm of angry trolls, that's his call.
I'm sometimes floored by the creativity of the DMs in similiar situations. Illuminaughty played the Grunstubhle foreman in such a vulgar, repulsive manner that my character obviously would have been disgusted and left ASAP. That's the stuff we remember and enjoy, and why we play EfU.
Lastly, even a little DM XP shows a player that his RP efforts are appreciated and noticed. This is not to suggest that I am a XP whore and that's all I care about, but even 50 XP to an 8th level character shows that the DM approves and enjoys their character. When that 8th level character can die and lose 9000 XP over a couple bad die rolls, what's 50-100 points in the big scheme of things?
If no XP is warranted, a polite suggestion via Tell or a later PM might help to elevate the players RP and thus the RP of the server.
Don't intend to step on DM toes here, but if I get even a snippet of DM XP, it goes a long way to reinforcing that what I am doing is adding to the server as a whole - and also invigorating and inspiring me to keep it up or to improve.
Great thread idea!