Where is the boundary between a game and a story? While it is true that it is possible to make a game without a story, there are actually very few games which do not contain at least an implicit story - a narrative situation. Indeed, these framing narratives serve to define the play of the game in many cases. What, then, is the relationship between game and story?
Let me begin by saying that I don't have an answer. Furthermore, this topic is so far from the testable that it is likely that there is no single answer to the question, and absolutely certain that the answers one will encounter will depend deeply upon the definitions of the terms 'game' and 'story'. For the sake of this discussion, I will use our standard definition of 'game' which is a tool for entertainment with some degree of performance (this may be something tangible like a victory or end condition, or something intangible, like the satisfaction of a table-top role-playing game session that just seems to flow perfectly). For 'story' I will cast the net wide and define it as any account of events affecting one or more characters (real or fictitious), and for 'narrative', as the specific delivery of a the details of a particular story instance.
What do people mean when they say "games don't need stories"? Because clearly, there are lots of games with narrative content, and many of them (arguably) perform better in the market place through the inclusion of a narrative, so it is not much of a commercial argument to claim that games don't need stories. I think, perhaps, they mean simply that the abstract, ludic content of a game can qualify as a game without a narrative of any kind. The clearest example is Tetris, which provides no narrative material at all in general terms.
It is true that abstract games can avoid narrative entirely, but this is not equivalent to saying that "games don't need stories", so much as it is saying that there are types of games which can avoid explicit narrative content. For instance, the "games don't need stories" point of view probably supports Quake in its absence of story. (Of course, Quake does have a story - a truly awful story, perhaps the worst ever written. But it hides it in the manual so that only a few of us have had a chance to share in its appalling cheese). But it is not that Quake is devoid of narrative - rather, the narrative situation that Quake presents is so inherently intuitive (kill all monsters) that it does not require any exposition. You could not remove this implicit narrative from Quake even if you wanted to.
Even highly abstract games have implicit narratives. Chess, for instance, is built from the implicit narrative situation of two kingdoms at war. Understanding this narrative framework makes the game of Chess easier to learn - because the idea that the game ends when the King is cornered follows from this scenario quite naturally, and the exchange of pieces can be understood as an abstracted battle. (Incidentally, I personally find Chess boring because the narrative is too codified for my tastes. For me, there's just not enough differences in the story of one Chess game and the story of another).
In the field of hobby games practically all games make use of an implicit narrative to provide the backdrop of the game - with the express benefit that understanding the actions and rules of the game becomes easier, because they have been given a context. Even a mass market boxed game like Jenga has something of a narrative to it - the aleatory narrative of who will cause the tower to collapse (the innocent version of Russian roulette). Perhaps, then, even Tetris has something of a narrative to it... after all, there is the potential of telling someone the story of what happened in a particular game.
One of the key values of a story in a game is that it simplifies the process of learning what to do in a game. When Resident Evil 4 sets the narrative framework that our bland action hero is looking for the president's daughter (the modern version of the classical Princess), we already know something of what is to be expected of us. It is not necessary to flash up explicit mission instructions, because our mission is derivable from the narrative context. Indeed, one thing that the Resident Evil series has done well is to draw from archetypal horror situations thus letting the implicit elements of its narrative silently guide the player's actions.
In terms of Caillois' four types of games, games of agon can eliminate all narrative elements - except the implicit story of two individuals vying for victory. Games of alea cannot eliminate the narrative implications of 'fate' - for this is the implicit meaning of chance in games (although culturally our attitude to fate has changed recently, and we are more likely to dismiss things as 'chance', even though 'fate' and 'chance' are concepts that differ only in their mythology). Mimicry and narrative are intimately intertwined. Only ilinx - games of vertigo - seem to escape a narrative content, but even here there is potentially a counter argument that can be made, just as we was made for Tetris. Although explicit narrative elements can be removed from all games, it is much harder to remove implicit elements of narrative.
Huizinga suggests that play creates culture, and I sympathise with this view. All human activities can be expressed as a kind of game (of varying degrees of seriousness to the individuals involved). Similarly, all human activities can be recorded as a story, and Frazer, Campbell and others have suggested there is an underlying framework in our minds which is adapted to accept and create stories. Is there a sense therefore that stories and games are counterparts to each other - that games create stories, and stories frame games?
At the moment, our technology creates games whose stories are severely limited - we do not have the technological complexity to support a game with implicit narrative as rich as a literary novel, for instance. And even if we did, we lack the widespread elegance of design to present such a game for a suitable audience. We could create a game with an explicit narrative with such complexity - but then we would not be telling the story of the game, but merely combining a complex narrative and a (presumably simpler) game together. Likely the complexities of the narrative would not sit well alongside the play of such a game, though, making such an exercise fruitless.
The art of making stories and games work together is to create each such that it is the complement of the other - another place I can use the analogy of the cast and the mould of a fossil. The play of the game should naturally lead the player through the story - the story of the game should naturally lead the player through the appropriate play. The more identifiably humanlike the avatar, the more explicit a narrative the game will support. Perhaps this is the reason games like Tetris seem markedly less narrative - it has no avatar, and therefore there is no character about whom to tell a story?
Since we currently cannot make games of sufficient (accessible) complexity to rival the heights of our best storytelling, we perhaps should focus on the other side of the equation. Games produce play and implicit narrative: we can look at ways of making those implicit narrative situations tie into an explicit narrative, thus deepening the sense of involvement (and the mimicry) of a game, and (crucially) of building dynamic explicit narratives which support whichever implicit narrative situations the player chooses to favour.
The footprint of a game's implicit narrative should therefore fit the foot of the game's story - or vice versa. We do not praise the skills required to achieve this, which we have called 'narrative-integration' (or design-integrated narrative), sufficiently within the games industry. We still judge game stories by similar terms to conventional narratives. There is nothing wrong with this - but we would perhaps benefit from identifying and praising those games which achieve an appropriate relationship between their play and their narrative.