I've heard the complaint that if a puzzle doesn't fit we shouldn't have it, but it is similar to the complaint that an rpg fight needs to contribute to the story. It's game play. It needs to somewhat fit with the story, but it doesn't have to be original or perfectly fit or anything else. It is game play added to the story, or actually the story is just something added to the game play, because a story without game play isn't a game but not vice versa.
I play turn based strategy or some type of puzzle game mostly. I don't see anywhere near enough variety in a shooter and in most rpgs that rely on action.. Once you put a puzzle in context, it's hard to recognize. They are really hard to write, I know that, because they do have to fit with the context of the set. I don't think games use enough puzzles, really. I don't think a game should be all action. It's like making the frosting the main part of the cake. You build up to a point to where action is the only alternative. Then again, I'm working on a dungeon crawler, but it's a strategy game.