I take a similar but different approach.When this happens, I remind my players that "Bob already did his very best, and failed. If you do the same thing he just did, in the same way, you will get the same result he just got." This pushes the ball back into the player's court--they must either think of a new approach to the problem, or move on.
I want this printed on a t-shirt, so that I can wear it to my gaming sessions.
I describe the dice toll for a skill check not as a judgement on the PC but on the circumstances.
Rolled a 3 on the search check? Lighting, debris, dust, excessive rot and fungus etc etc are hindering the search. You *know* it was not a good search. So, you dont have to think it's the best effort but the worst condition.
Which gets back to "so how do you change the conditions?"
That combined with the setback rule for failures does wonders for flavoring skill tasks.