I went for the "mixed" response.
Generally, my random encounters will be fixed to be challenging but not likely to kill. They will almost never be easy, but that's because my random encounters are generally well spaced, and if easy they just become Wandering XP.
However, I have no fear of placing stuff completely out of the players league in their path, so occasionally a super-tough random encounter may occur. Almost all of my "random" encounters are pre-rolled, however, so I'll have a chance to think about a situation and prepare some "outs" for the party ... whether they take them or not is antoher issue.
On encounter strength in general, my party at the moment (6 x lvl 3 PCs) is wandering through a forest occupied by a dormant, adult, green dragon; a wierd magical tower that currently they couldn't feasibly survive past the fifth level (if that far); an orc tribe they'd be hard pressed to defeat; an underdark entrance where they almost suffered 4 out of 6 deaths because a couple of them didn't believe the deurgar could call up a 100 friends (in the end it just cost them 200gp and some dignity to leave with their lives); and the crypt they're looking for, which would probably kill them at the moment.
They know there's supposedly a dragon about somewhere, but they didn't gather a lot of info before setting forth, so it was a joy to see the reaction of some of the more experienced players when they found out they were adventuring on the doorstep of the underdark.
However, if they play it smart, by the time they find the crypt they'll be capable of finding what they need inside and they'll have a lot of places to come back to later.
Let 'em be heroes, I say, but keep them on their toes and keep them aware that its a big, bad world out there.