Greg Costikyan has already said more enlightening things about story and games than I could ever hope to.
But I'll share my thoughts anyhow. My thoughts on the matter have changed over the years. When I was a teenager I immediately noticed a difference between games that didn't have stories and games that did - with an endless just-gets-harder game like Defender, you get bored at some arbitrary point and quit playing. With a game that had even a rudimentary story, say a game like Karateka, the stop-playing point came at the conclusion of the story. And that was just more satisfying than quitting a game because I was bored or frustrated. The conclusion? Games should have stories, to motivate the player to keep playing. When playing games I rarely gave a crap about my 'score' - I just wanted to get to the next level or get to the end. (No leaderboard servers with your friends' list highlighted in the 1980s...)
But that was the problem, right? You get to the end of the story and you're done for a different reason. The ideal, it seemed to me, would be a game that could generate infinite stories. I imagined something like *Fable* was supposed to be, the *Fable* that never was, a rich interactive world where story would just happen because of the interactions of intelligent characters. I didn't stop to think that we already have that, and it's called "life", and those storytelling moments, those moments that are worth retelling, they are oh so very rare.
I've spent a fair amount of time trying to prototype this imaginary game, and what I ended up with was like a fantasy version of *Space Rangers 2: Attack of the Dominators*, except with relationships. And whenever I showed it to someone I couldn't help but notice that they were underwhelmed. The final nail in the coffin was discovering *Space Rangers 2*, which was like seeing my own game with fresh eyes and realizing it just wasn't fun.
My prototype wasn't much of a storytelling engine either, for that matter.
So I said to myself, "Forget story, let's just turn this prototype into a fun game." And suddenly, boom. There it is. Something fun. (For me, anyway.)
So let's call that Exhibit A.
Something I asked myself recently was, "What games have stories that were so compelling I'd want to read the novelization or just watch all the story-moments (cutscenes etc) back to back without actually playing it?"
I can't think of any. The best I can come up with is there are a handful of games-with-stories which would be impossible to tell as just stories - Bioshock, for one. Portal. Soul Reaver, although Soul Reaver had the arrogance to end halfway through with an Empire Strikes Back ending as if it was a sure thing I'd come back to it for the sequel. I did, eventually, I think, but by that time I had long since stopped caring so I never did make it to the end of the story.
Let's call that Exhibit B.
Lately I've been playing D&D with guys who are firmly in the gamist wedge of the narrativist-gamist-simulationist pie. I used to think roleplaying games were for...well, roleplaying. And storytelling. And although I had noticed that the times I used roleplaying as an outlet for my frustrated writer's syndrome were never as satisfying as those times when I was playing some off-the-shelf module or a generic dungeon crawl, I hadn't yet drawn the conclusion that storytelling games just aren't that enjoyable for me. It wasn't until, now, playing with these guys that I realize truly that I'm having more fun moving around the miniatures, rolling dice, and making tactical choices than I ever had playacting a barbarian with a hokey irish accent or playing Universalis. The real eye-opener was when we took a break from D&D to play various board games like Descent and Hero's Quest - I used to think that these sorts of games, these RPG's without the roleplaying, got it all wrong, "That's not what RPG's are supposed to be about," and here I am discovering that they can actually be more fun to play than D&D on a slow night.
So that's Exhibit C.
When playing almost any game these days I have "story filters" active. "Just tell me where to go and who to kill and what object to retrieve." Some games make it particularly easy by highlighting quest words in the dialog trees. Others let you button-mash through the dialog trees and it's ok because they'll pop a quest on your quest list and an arrow for where to go on your HUD. And you might say, "Sure, but that's because most games have bad stories." But I'm also talking about some critically acclaimed games where the stories were allegedly excellent.
So, over the last 20 years or so I've gone from "games are a fantastic new storytelling medium" to "Stories just aren't fun. If you must have story in your game, please keep it to a minimum, and ideally something like *Ico* where you don't even need any dialog to get it across."
What really motivates me to get to the conclusions of these games with stories? Now I think it has very little to do with wanting to find out how the story ends, but rather it's coincidental - it's partly the completionist tendency to want to color in the box completely, clear the pacman maze - and partly because that's when you get to the end of the game's content. The holy grail for me now wouldn't be the game that can create infinite story - but a game that could procedurally generate infinite interesting content.