Havn't read it all, but here are my thoughts!
* Taking 20 does not guarantee success!
Just put some nasty traps in, that the non-Rogues are not able to find (DC 20+, see the Rogues Trap ability). Once they have sprung one or two traps while searching, they might become a little more careful, or leave the job to the pros!
* Wandering Monsters!
Well, this has been said often times already.
* Time limit!
Give them a time limit to complete their task, if applicable.
* Let them!
If there is no reasonable time limit, and they really want to dig in the dirt for days, then just let them!
* Disappoint them!
You could describe with colorful mental pictures and to all extend, their heroic

search of the dungeon room, which takes hours. Take your time. Describe this scene for 15 minutes or even longer, if you can do that. When they do it again, repeat the process. They should get a feel for how bored their chars will be after a few rooms.
* Encourage Take 10 or Roll Thrice!
Take 10 is a great rule for such an occurance, but most players are aware, that they can't get to high results using this technique, and therefore can miss something. Roll Thrice is a limited Take 20, you just roll three skill checks and take the best result, takes three times as long as a regular application of the skill, obviously. It's pretty good for a careful but not excessive Search.
Bye
Thanee