For your specific issue where they're constantly looking for something where nothing exists you may need to react differently depending on the circumstances, but there are two basic scenarios. Time-dependent and not.
If time is of the essence, keep track of how much time they're wasting per search check. You'll want to let them know this, of course - simply saying "Whelp, you're out of time!" out of the blue could end with unhappy players. On the other hand, if time is not critical - remind them they can "Take 20".
(I realize this is tagged as system-agnostic, but as GM you can probably grant your players something similar even if the rules don't have that built in.)
As a reminder - from d20srd.org:
A skill check represents an attempt to accomplish some goal, usually while under some sort of time pressure or distraction. Sometimes, though, a character can use a skill under more favorable conditions and eliminate the luck factor.
Taking 20: When you have plenty of time (generally 2 minutes for a skill that can normally be checked in 1 round, one full-round action, or one standard action), you are faced with no threats or distractions, and the skill being attempted carries no penalties for failure, you can take 20. In other words, eventually you will get a 20 on 1d20 if you roll enough times. Instead of rolling 1d20 for the skill check, just calculate your result as if you had rolled a 20.
Taking 20 means you are trying until you get it right, and it assumes
that you fail many times before succeeding. Taking 20 takes twenty
times as long as making a single check would take.
Since taking 20 assumes that the character will fail many times before succeeding, if you did attempt to take 20 on a skill that carries penalties for failure, your character would automatically incur those penalties before he or she could complete the task. Common “take 20” skills include Escape Artist, Open Lock, and Search.
I know Pathfinder & D20 modern have similar rules and I would imagine other game systems do as well - but again, if they don't; as GM don't be afraid to add them in if you feel it would fit.
So when you have someone take 20 - plus all their skill/attribute bonuses in search - plus someone assisting them, and they still can't find the thing that doesn't exist in the room you can say "After hours of searching the room with a fine-toothed comb, you find... ~dramatic pause~ ...some lint."
As for broader cases where meta-gaming would lead them to do certain actions - switch things up! They think trolls are vulnerable to fire? Nope - you have to freeze their wounds, instead!
For other things - like "sense motive" - let your players decide when to use it. If they don't trust someone and fail they can continue not trusting him. Failure shouldn't mean that they get the wrong impression, just that they don't get any impression at all.
TLDR: Don't be afraid to remind players about "Taking 20". Switch things up if they require knowledge-checks for the characters to know it even if the players already think they do (get creative! Trolls are vulnerable to ice, not fire!). Also, checks should determine how much information players get - not to give them wrong information (which they will metagame around anyway) - let them come to their own wrong conclusions instead of trying to force wrong conclusions onto them.