I reckon there's an important difference between a challenge being frustrating because it's hard, and a challenge being frustrating because there's no interesting way to approach it. Hard puzzles can be fun and satisfying to solve (albeit frustrating at some points along the way) when the process of solving them involves doing something clever or creative. But when the difficulty arises because the solution is basically arbitrary, and so I just have to do a brute force search, that's a tedious waste of time.

The boundaries can be blurry, and a puzzle can wrongly seem to fall into the tedious category because I'm missing something. But, in my opinion, classic adventure game puzzles too often really are arbitrary and boring.

I agree but IMO it's better to have a puzzle that's frustrating because, like you say, there is no interesting way to approach it rather than just have easy puzzles.