I agree with that, a big part of the "puzzle" aspect is that it shoudl get _HARD_. There are plenty of platform puzzle games (trine comes to mind) which are fun, but they aren't really hard. As a child of the 80's games I really find game reviewers that complain about how hard games are to be silly. That was a time when the idea of saving your progress was foreign. There is nothing like having to play a game for an hour to get back to the point where you died.

I think a good recommendation might be FEZ for a game with physical puzzles that get incredibly difficult.

Although, even machinarium (which was in humble bundle2 with braid) has some pretty fun puzzles in the form of a point and click adventure.