For me, this has always been things the player, not the character, must figure out, It can't be adjudicated by a simple die roll against a skill, trait or stat.
Typical example is a series of Call of Cthulhu clues that have been handed out to the party that once deduced, point to a potential location or event in the adventure. There is no "roll" to tell the party where to go next or what to do.
Another example is an in-game riddle that is solvable with what the party knows (more clues can be made available possibly with knowledge checks), but that the ultimate answer to the riddle cannot be solved with a die roll.
In both of the examples, the clues should be fairly solvable and players should be given as many clues as possible, but solving the puzzle through a dice roll is anti-climactic and removes the good feeling players get for solving the puzzle. I agree it can be frustrating if the puzzle is so obtuse that it could never be solved with common sense or one that doesn't serve everyone at the table.