The next time...
... your elf fails a secret door check, they really DO feel something is odd about that wall and that secret door is right there, plain as the nose on his/her face! It must be magical!
... your dwarf fails a detect traps check, every 10 to 15' or so, he/she sees another trap, very similar. This continues on for another 1d6x10 feet.
... your Magic User fails some sort of an attribute check against their Intelligence, or Saving Throw, say to suss out the arcane formula that either explodes like a fireball or gives him the Big Secret... well, he's for sure he's got it right... all we have to do is displace that dragon 3 days over and then grab the cocktrice's tail and...
... your thief type character fails to detect traps, she really DOES find a trap and spends quite a few turns trying to disarm it, but for some reason, it's not working.
... your fighter fails to open a door, no, he really does open the door and keeps on steaming through the room unbalanced, falling over everything and slams into the other side of the room, knocks himself out for 1d6 turns/rounds (rounds if there's gonna be combat from the other dudes looking in amazement at the idiot human who just knocked himself out...) and worse indignity, suffers 1d2 points of damage from the crash and door falling on his face.
Failure doesn't just have to be "No" - take what would have been a successful outcome, or what would have happend IF there was really something there, twist it so that it's going to be an obstacle or setback and make it a red herring, an event that wastes time/resources, puts them on a temporary bad path... something that they'll talk about for months down the road - "Hey, remember when George tried to kick open that door that led to the Imp's breeding grounds and he knocked himself out falling right at the feed of the Barbed Flaming Devil?!?"
 I love the 3d6, 4d6, 5d6 or 6d6 attribute check dealio. Not only are you rolling a lot of dice, but it's intuitively cool.