I think the main thing that should be avoided is the need for someone who's hopelessly stuck is the need to tab out of a game to look up the solution. I'm someone who does genuinely enjoy finally reaching that "Ah-ha" moment, yet if something is set up merely to impede progress rather than contribute to the story and pacing of a game, I can easily get frustrated and look it up, and if I have to look up solutions more than a couple of times I just stop playing because that's no way to enjoy a game.
I like the solutions you bring up, and I also start thinking about the older Silent Hill titles and their puzzle difficulties. On the Beginner setting, the clues were much more plainly worded so it was easy to sort out a puzzle, whereas on the harder one's they require careful re-reading of notes and much more trial and error to figure things out. I use this puzzle in particular as an example: http://silenthill.wikia.com/wiki/Coin_Puzzle.
tl;dr In summation, maybe there should be different difficulties so everyone's happy, such as noobs like me and adventure game vets.