Horror in a game is a difficult thing to achieve. There is always the thought that you can just simply reload/respawn if anything goes wrong, which basically eliminates any fear of death. Using cliche's for horror also hurts, somethig that many games are guilty of. I have seen about 10000 zombies now, they just dont invoke fear anymore. I dont believe being the "hero" is the problem per se, but knowing your the hero is what invokes the feeling of indestructability, and the insignificance of everything around you.
As stated, perma-death would bring back some seriousness into dying, but for linear games it wouldnt work. The game would lose any horror effect if you repeated the same segments over and over. The SCP game though shows that randomness in a horror game has alot of untapped potential. It brings unpredictability, and allows for non-fustrating perma-death. However, dying over-and-over can trivialise death.
What generally makes horror horror is that you *dont* really know what is happening. It causes the mind to think up unwanted and uncomfortable scenario's. With games like Left 4 Dead, this doesnt happen. Nothing unexpected happens. Shoot some zombies, shoot some more. Same goes for Dead Space, just zombie shooting. Thats not to say that they are bad games, just that they dont really invoke horror. (The aminated deaths in Dead Space diddnt help either. Seen-one-seen-them-all little clips of animations seemed pointless.)
Amnesia tried to mind-screw the player into fear, and it worked quite well. It felt less formula-based, and more like something could change at any moment. The lack of "gamey" elements plus the great visuals and atmosphere was a huge contributor. Plus the story had you pressing further for more of it against the natural fear-of-the-unknown the game invoked.
I dont believe the story is critical to a horror game. The story in Amnesia I diddnt find particularly "scary" (at all). If you ignored the story in Amnesia it is still scary. Games can use visuals and ambience to stimulate the mind into imagining what could have happened, and what could happen. This alone can create a feeling of dread and horror. Throw in some randomness/unpredictability, and vary the game (so that it doesnt feel so formulaic, or even remove it) and IMO thats on track to a genuinely scary horror game.
Basically, A truely scary horror game is quite difficult to do. What makes a game a game tends to work against-the-grain of horror.