While the question is about investigation at large, I think this issue comes up under a few very specific situations. A failure to account for the PC's failing investigations is present in campaigns that focus on solving a mystery. Indeed, even a single investigation-solved event is a tiny mystery. People get into the whole sleuthing, cop-show, Sherlock Holmes mode of story construction when they think about investigation in RPGs and I'm going to address this larger issue to address the issue of investigation in RPGs in general, because they are all part of the same underlying issue.
The seeming problem
Lately I've been thinking a lot about how to make satisfying investigation scenarios in RPGs. The typical advice is that the GM should construct their mystery with a set of clues that lead the PCs towards the final conclusion and provide a reasonable number of avenues for them to find the clue.
The problem with this is that even when a 'clue' is assumed to be a piece of information that could be gathered and the format of the 'clue' is assumed to be variable - The killer used a baseball bat, Old Tom likes baseball, and the PCs can discover this by finding his memorabilia in his room, or asking his wife, so on - you are left in a situation where a PC has a skill, and that skill is used to decide success or failure of uncovering the clue. Yes, they have more chances to uncover the clue, but that doesn't ensure success and - as you noticed - investigatory campaigns tend to treat success at finding clues as a prerequisite for advancing the plot.
I've also seen solutions to this problem in the form of simply giving the players the clues and not consulting their skills. This is probably a good solution if your game of choice doesn't model investigation, but a players that invests in investigation skills will feel cheated if those skill are never used. And while you can probably fake through a lot of investigation by letting them roll, fudging numbers and letting the bad guys make mistakes to help them along, these are all dodges to the underlying problem with investigation as modeled by those games.
I've also seen a lot of metarules that, rather than letting these skills control success or failure itself, these rolls/skills determine how much the GM explains about a given situation. So if they PCs all suck at investigation, they might get this text "The room is seemingly empty" and if they are good they might get "The room appears empty at first, but as you walk into it the floor squeaks" and if they are awesome at it they might get "The room is intended to appear empty, but a squeaky hidden trap door's outline is visible to you on the floor."
While the above certainly works to better model the ability of the PC's character by giving the player only the information the PC would notice, it doesn't take into account that players themselves have various ability levels. It also requires a lot from the GM. And aside from all that it still doesn't address the issue of what in the world happens when a PC fails!
The real problem
After a lot of thinking and research I've come to see this problem from a different angle. What exactly is the difference between an investigation and your typical RPG quest? From a world-building perspective there really isn't a difference. To see this it really helps to build your campaigns from the perspective of what will happen if the PCs aren't there. Take this example:
Evil McEvilson wants the gold in a secret room behind the throne. The King, Doofy Doofer, doesn't know this room exists but doesn't like letting Evil into his castle because Evil once told him he's ugly. So Evil disguises himself as Joe Everyperson and pretends to be a visiting dignitary. If no one stops him, he'll slip poison into the night guard's food, wait for night, and sneak off with the gold in the morning.
In this situation, the PCs have a variety of ways to blunder into stopping Evil. They might succeed on detecting his evil from the start, they might be in the room trying to steal things themselves, they might stumble on the guard, they might do any number of things that Evil will not like and that will win them favor with Doofy in the morning. But they also might do none of these things and be asked by the King the next day to investigate the strange room they found behind the throne.
This scenario could be presented either as an open-ended situation that just is happening in the world the PCs are in. Or it could be laden with clues and people of interest that know this or that and so on. Do you see what's happened here? Investigation stories are railroading!
What is railroading? Railroading is when the GM has a specific thing he needs the PCs to do to progress his own agenda for the story. They need to find X because finding X makes them want to do Y and Y leads them to Z which involves this other cool thing about blah blah. Railroading is when the GM's idea of what the PCs should do conflicts with what the PCs are inclined to do and so he has to encourage them to stay on the rails. Sometimes that's gentle encouragement in the form of an NPC insisting on something. Sometimes it can be as bad as the GM stating flatly they he didn't prepare anything down the left path (since it is covered in flaming blood) but there is so much fun adventure down the right path that is bathed in golden light!
Railroading is generally a bad thing. It isn't always, sometimes a campaign goes so far off the deep end that a little encouragement to get back into something more fun for everyone is in order. A good use of railroading is when the GM is just getting the players out of something boring (like if they decided to setup a store and now are dealing with endless waves of customers) and into something fun. But often railroading is simply how a GM avoids work or pushes the PCs into some adventure they have planned that they think is cool but there isn't sufficient motivation for that PC to really be interested in on its own.
A mystery is generally a very specific situation that happened in the past and that needs to be unraveled in the present in a certain way to keep it suspenseful. This means that if the PCs just knock down the wrong door, they will stumble on the captured maiden and ruin all the fun the GM had planned for them.
The reason it is so hard to create suspenseful mysteries in RPGs is that their construction is at odds with what being a fun campaign is all about! Injecting them into a game that wasn't specifically designed for running mystery games, is antithetical to the player-driven storylines of most other game systems. They overemphasis the role of the GM and diminish the choices of the PCs down to even the choice or possibility to fail.
Ok, So what can be done.
GMs are served well by designing their sessions around a potential future that comes from an already established past. So-in-so did this, and plans to do that, unless someone stops them. The great flood is coming, and it will kill everyone unless someone does something about it. If the GM is answering the underlying question for the PCs, then he is doing it wrong. It is fine for him to decide ahead of time what will happen if they do X. But they have crossed the line once they decide to artificially convince the PCs to do X.
This isn't to say that a little railroading is always a terrible thing, but that there is a difference between placing a coil of rope at the edge of a cliff and getting the PCs into a boxed canyon that leads to a rope already hanging down the cliff where there are birds that will come to peck at them and when they get to the bottom there is a river and a raft they need to take to... You get the idea.
A good GM will get to know their PCs over time and will be able to predict what they are likely to do so they can plan for those things more than the things they aren't likely to do. Given this, it is possible to construct a mystery that the PCs are likely to be able to solve. But as soon as you assume they will solve it, you've made a big mistake.
Consider this situation:
The PC's stumble on Evil McEvilson sneaking out of the throne room with the loot. Up until this point, they missed every clue that he was going to do this. They talk to him and he lies saying he just got turned around and was heading to his own room after getting a snack. The PC's buy it and go to bed. In the morning, Evil is gone! The King asks them about it, thinks they are idiots and demands that the PCs hunt down Evil to the ends of the Earth!
This is a total failure on the part of the PCs. They have not found any of the clues, they have not succeeded with any investigation skills, but the world went on without their success and now they are charged with redeeming themselves. This is still good story. It was a failure for them, but it wasn't a failure of the story.
