The japanese are pretty good at making these kinds of games, strange little puzzle adventures that are totally bizarre, but awesome at the same time. One of my favourites is Kesamaru on the Gameboy, a random rom I found in the batch my brother gave me over 10 years ago. Another great is Bubble Ghost, also on the GB.

I'm pretty sure Point-and-Click Adventure games count towards puzzles, so I have to point out (unnecessarily) the sheer awesomeness of the Lucasarts games.