I’m not sure that I understand which kind of games can be classified as “puzzle-based”, because I’ve seen that the ones that I consider puzzle-centered are sometimes labeled in a different way by other people.
Also, it seems that all the puzzle games that I played in the past had at least one pinch of story in them or they attracted me from an artistic point of view, so the games that I’m about to list are different from the one that I have seen listed in this thread, although their gameplay is still based strongly on puzzles.
Said that, I have played The Room, that from my point of view is based way more on puzzles than on the story.
Can Windosill be considered a puzzle game? I don’t know, but I’m citing it as well. I liked its surreal environment and puzzles can be considered “logical” only according to the characteristics of this surreal world.
I’ve also played the demo version of Gorogoa, that you will not find on the official website but that it’s easy to get from other sites. Gorogoa is all about puzzles, but from a strange graphical perspective. It’s one of the most original games I’ve played in the last years and I warmly suggest you to give it a try.
I have also played “casual” puzzle games, like “Cut the rope” and “Triple Town”.
From the games that you mentioned I think that I would enjoy TIS-100, assuming that it has no time limits.