In general the game needs to support trial and error without punishing the player. If it takes too long to execute a solution then I'm going to be afraid of experimenting and board at the end.
In an open world game if it takes too long to travel between destinations, I'm way more inclined to pull up a guide when I can't find what I'm looking for.
I think the core problem is scale. a puzzle, once the solution is discovered, typically take under a minute to execute.I think this is the big issue.
open world RPGs, where discovery mechanics are most prevalent, may require hours to execute. the good/bad of the quest log is it tells you what to do but also reminds you of what you were doing.
I think when it starts feeling like "Discovery" is actually getting in the way of the game, that's when it stops being fun. If you have to spend 20 minutes, or even hours trying to figure out what to do or where to go, that's not fun.