The problem I have with people critical of game stories is that they seem to have no knowledge of adventure games, and the game mechanics that make them up.

I wasn't fully with you on story as mechanic, and maybe I'm still not completely, but I thought your closing paragraph was strong.
In that paragraph, the narrative takes the role of a "hint" system and I think it's likely you could describe a hint system as a mechanic.

I am annoyed at people defining "games" as replayable, and systematically driven.

Puzzles are not replayable. You figure out a Rubik's Cube and, well, there you go, game over. Finish a crossword, you're done. Put all the pieces of a puzzle together, why break it apart and do it again?

It's easy to define a game as the the thing that best supports the argument that you're making and then say, "Look! I'm right."
However, except for your hint system example, I would say that most often narrative isn't a game mechanic. This is not to say that it isn't important. It is often the main reason for playing.

The game mechanic that I find critics most often overlook is "exploration."
Finding stuff. It's a powerful mechanic, because its pretty easy to program and it gets to our cave-man brains. Click around and get a reward.
Click in one spot and get a joke.

Solve a puzzle in another and you move the story forward. Release the happy hormones. Look how smart I am! It's your reason to play.

Exploration isn't "replayable" as such, but it isn't bad game design. It's just the nature of that game mechanic. Add enough stuff to an exploration game and it becomes replayable. The player might miss something. Over the course of a 30 hour game, the player might forget something. Then, it's fun to go back and see it again.

Is Myst, the best-selling computer game of all time, not a game, because it isn't "replayable" in the "Baseball is replayable" sense of the word?

But critics need to actually understand why genres use different mechanics and how they differ from each other. Saying "Doom" is better game design than "Myst" is tinged with more than just a bit of academic posturing.

In certain genres, story is a must-have.