Tell me [the PCs] can fail as well as succeed. Tell me they can come back to the King and report they didn't rescue the Princess because (unknown to them, of course) they missed the main clue to her kidnappers' location due to searching the Duke's desk instead of the Chamberlain's. Tell me they can't get to the Throne of Antioch because they didn't find the throne room key in the haunted cavern and the door won't open any other way.
In my games the PCs absolutely can fail, but it's a very different kind of failure than you're talking about. At my table the PCs fail at a particular goal as a result of making informed (or apparently informed) strategic decisions. So, for example, they might fail they when they don't or can't devote sufficient strategic resources (e.g. time, money, influence), when they're operating on faulty or incomplete information, when they prioritize other goals, or when they rely on a strategy with a probabilistic outcome (e.g. combat) and chance doesn't go their way. I find these kinds of failures have a
positive impact on the game, because seeing the game world consequences of their high-level decisions emphasizes the importance of the players' choices.
But when the PCs prioritize a goal, formulate a plan using accurate intelligence, devote more-than-sufficient resources, and don't engage in fights that they might lose, I'm not going to let them fail just because it didn't occur to the players to search the Chamberlain's desk instead of the Duke's desk. They're either going to find what they're looking for in the Duke's desk, or (if there is enough time remaining in the session) they're going to find something that points to the Chamberlain's desk. In my opinion, failing because they didn't think to engage with the right environmental feature(s) of the setting has a
negative impact on the game, leading to the players getting frustrated and a sense of a wasted session. Instead, I'll give the PCs the success that they "bought"--after all, it came at the cost of failing (or at least delaying progress on) other competing goals.
Of course, success isn't all-or-nothing. If the PCs did all of the above except they were acting on
inaccurate intelligence, they're going to succeed at getting information from the Duke's (or the Chamberlain's) desk, but maybe it's information exonerating the Duke, rather than revealing the location of the kidnapped Princess. The PCs "failed" at their goal of finding the Princess (possibly permanently if there was a tight deadline), but it was the strategic decision to go after the Duke that caused the failure, not a failure to correctly interact with the environment.
To briefly apply that point to your other example, at my table the PCs might fail to get to the Throne of Antioch because they searched the
wrong cavern for the key, or because the right cavern was too expansive and they didn't bring enough help to search the whole thing in time. They're not going to somehow fail to find the key despite looking in the right location and devoting enough resources to the task.