I find it a bit amusing that noone bothered so far to mention the Myst games. Those games are quite straightforward what the use key on door concept is conserned, but the complexity of most puzzles is so vast that using a brutforce approach to crack a puzzle implies millions of permutations of the given combinatory dataset. You had to search for clues as to how to solve it, and some of the puzzles gave me quite a lot of headaches (literally).
Another game of interest in this genre would be Shivers 2: Harvest of souls. It's puzzles can't be compared to the nightmarish puzzles of Myst 1-5, but the eerie and creepy atmosphere of the game made it allmost impossible to solve the complex puzzles without putting them down on paper, turning off the computer, solving the puzzle offline, then start the game, and try your solution.
What I'm trying to point a scrutinizing finger at, is the singleminded focus on the "use key on door" phenomena. Game developers can easilly make an above par puzzle game (or even excellent puzzle game for that sakes matter) if they pay attention to the psychological and mathematical factors of any puzzle. Make the puzzle complex enough (i.e. permutations of possible solutions > 1000000), and add a suiting (i.e. extremely distracting) atmosphere to each scene, and you'll have a nice graphical game with the potential to leave the player breathless whilst giving him her quite an intellectual challenge (which is in fact required to solve a puzzle).