Fenixp: Have you tried The Longest Journey and it's sequel, Dreamfall? Granted, there is one or two illogical puzzles involved, but the rest either makes sense or is not puzzle at all. Saying that the only genre that actually focuses on good story should stay dead isn't the best thing to say, in my opinion. You should rather think 'Adventure games should be more polished.' They have some game design issues that are usually not resolved even in today's games, but still, they work great as interactive fiction, and that is the way I actually approach them. You are right about them not basically having gameplay thou, not that I actually care about that since I'm playing...walking trough them for story.
Kudos for trying WoW before bashing it. :)
I do in fact have TLJ installed, but I haven't been bothered with getting it to run yet. (It's the GOG version, yeah). I do kind of regret that I couldn't find the version with Swedish dubs; the one time I want a localized version of a game and it's not available...
Even if I look at adventure games as interactive fiction, well, it's only interactive if there's actual gameplay. Granted, my favourite game evar, Planescape: Torment, is pretty much only text with zoomed-in pixels, and it's why I love it, but it's still more interactive than ye average adventure game.
I recall trying one of the old Infocom games a few years back - Trinity - and I found it more interesting than any graphical adventure game I've played simply because of the illusion of freedom in it. Granted, its difficulty was stiff enough to make me drop it after a few hours, but it still seemed more genuine as a game compared to what was released later.
On the whole I feel that Valve are on to something with Half-Life: you tell the story in the medium, not try to make the medium something it's not. I still love Final Fantasy and Metal Gear Solid and all those games with fancy cutscenes, but it's definitely not how story-telling in a video game should look. Even the floating text in Braid means you have to pause the action to read it, and that's one of the best examples of story-gameplay integration.
I recently saw a screenshot of the new Splinter Cell where the main character was crawling through an air duct (absurdly spacious, of course) and light was filtering through in such a way that the words "Save the scientist" (or somesuch) became visible on the wall. That seems the right way to go.