I think saying that a game story doesn't work because you can always reload and try again or try something different is like saying a story in a book doesn't work because you can always stop reading and never see the end. That doesn't really make sense to me. The narrative in a book isn't any less a story because you don't bother to read the whole thing.
The issue is that game stories have quite a different dynamic to traditional stories. Lajos Egri, in his book The Art of Dramatic Writing, distils our ideas about theme, meaning and the moral of the story into one idea that he calls the 'premise'. Basically the premise (in Egri's terminology; not whatever else we might mean by the term 'premise') is a statement that the story is a process of demonstrating or proving. I spent a lot of time about a year ago sweating about how that applies to an interactive situation that might or might not demonstrate this statement. In the end, I realised that it doesn't. To me, the 'premise' of a game is not a statement, but a question, and the process of playing the game is a dialectic process by which the player can answer that question. It's true a lot of (all?) games don't capitalise on that, but I think not many people have even realised it yet. But in that sense, exploration of the story themes and those glimpses of alternative outcomes that are not part of the final actualised narrative (e.g. when you die, which isn't part of the 'real' story, rather than rescuing the princess, which is) are essential for contextualising and giving meaning to the path through the story.
So the problem is that we judge game stories on the level of traditional stories, and we assume that anything that is not 'saved' into narrative memory (e.g. by reloading) is not part of the 'real' story. That makes sense in that that's what game stories by and large try to be, but we need to get away from that if game stories are to be what they should be.