What kind of story does Portal have?  I see a series of puzzles, and GLADOS taunting you in very humorous ways.  The game has a goal of completing multiple puzzles.  I don't see a story.  I do see how the game could be used to generate a story, but the game itself doesn't really have a plot.  It does have some interesting stuff regarding the background though.

You don't need a story but it can make a game better.

Of course it has a plot, simple and twisted as it might be.

You're not only presented with a few characters in a setting, but their roles and interaction change in a meaningful way.

During the game you're revealed additional information about Chell, and as you go on you start seeing cracks revealing the backstage beyond the aseptic test environment, leading to increasingly distrusting the very tutoring authority that led you through the previous areas. Then you move from the "test chambers" to the deserted backstage area, ascertaining GLaDOS' madness. That's a very proper "plot twist". You have a final confrontation during which you learn even more about GLaDOS' personality. Then there's the closing sequences which brings even more clues about what you just saw.

Saying that it has no story would mean that there's no narrative value in the order in which you're exposed to the details, dialogue and environment. But if you -in an ideal experiment- were to mix and swap some of the later scenes of the game with the ones in the beginning, then you'd clearly break or at least change deeply the progression of how you, the player, read the characters and the situation.

That's basically the definition of story: the scenes and events gain additional meaning by the order in which they're exposed.

Now you are talking crazy. Portal has a very clear story. Without the story Portal would have been a great game. With it though, it's the best game of all time (my firm opinion). The compliance/escape/revenge theme that runs through it is similar to Half-Life 2, but with only two characters and much better use of enviroments the storytelling becomes so much more focused and rather impossible to tell from the gameplay.

It's the second best example of storytelling in a game, in my opinion.

I saw the OP as attacking the idea of games that rely on storytelling. But you seem to have backed off of that or denied that you meant that, as the case may be.

So I'll just say this:
Do games need stories? No.
Do books/stories need words? No.

In fact, I just pulled out a very fun little book called Tuesday (by David Wiesner) to look up support for my point.
http://en.wikipedia.org/wiki/Tuesday_(book)
(In point of fact, there are words in the book: "Tuesday evening, around eight." But they could just as easily have been omitted with no ill effect.)

May I have a chocolate biscuit?

Oh, well done.  I was going to respond to that, but I don't think I could probably say anything you didn't already say better. 

(AKA "QFT")

Half Life 2 has a pretty clever story, but Valve took the approach where its up to you whether you dig into it or not, which I think is the best way to go.  However, just because you chose to play the game without bothering with any of the deeper backstory doesn't change the fact it is there.

TF2 is a pure multiplayer game - of course it has no story!  I play it lots and love its zany humour, but that's exactly the kind of game that doesn't really have nor need a story - it has a carefully implied context to give it a setting, but that's not a story.

Some games are definately going to need stories, but of course many, perhaps most, don't.  Take Uncharted 2 - it simply wouldn't work without its Saturday morning adventure serial story and context, it's characters are too well presented and it's world too realistic to work without a narrative.  Bioshock whether you like the story or not certainly wouldn't work without one IMHO.  Again, the setting is too rich.  There needs to be a story.  I thought the story in Bioshock was weak in the end, although the game started well, but that's the problem - those games that do need stories all too often have weak ones.

Basically, anything like Fallout 3, Uncharted, etc. do need stories.  Those are games.  You're last line is in conflict with itself. You can't say games don't need stories but text adventures do.  Text adventures are games - ergo some games need stories.

I basicly just skipped all the plot in Fallout 3 and it was boring like hell for me. But i still enjoyed the world/setting and the gameplay.

So yeah basicly games don't need to have a plot b/c the really interesting "story" is created by gameplay and is unique to each players experience.

Now games which heavily rely on plot have a gameplay problem OR are here to tell a story in a game's way(FF, Adventures).

Plot can help the gameplay to explain some mechanics or to amplifie the immersion and so improve the experience.

What plot shouldn't be is the only motivator to play a game. B/C then it's not the game what motivates but the narrative.

Story Games are the best, i think.

Bsp. metal gear solid 4, best game ever