In Spycraft 2.0, which leverages the skill system strongly, one common class ability model is the so called "flawless X". The sleuth class gets it for Investigation and Sense Motive, the Snoop gets it for Analysis and Search, and the Explorer gets it for Athletics and Culture. There are others.
What these class abilities do is, unless you really screw up, if you fail a roll, you are considered to have succeeded if the DC is less than 20+class level.
I am not very familiar with Spycrafts rule but I think that may be a good way to handle things. However I like Chucks idea of limiting rolls as much as possible so they don't "get in the way".
As to your mystery adventure style of play, that is how I typically do things. Failed rolls result in the loss of extra info. The other technique I use is not to remove the extra clues, but instead give the PCs access to them in a more delayed fashion so that they might not solve things as quickly.