"One of my players wants to bypass the game-play by saying 'I search everything'. I've responded in the past by asking them to be more specific, but this isn't working well."
This sounds like a source of irritation to both the Dungeon Master, who doesn't want his work bypassed, and to the player who doesn't want to jump through hoops. This interaction can end up being very confrontational.
The solution is somewhat non-obvious. I generally try to never approach an interaction in a game by asking a player to do more. I maintain agency with this the same way I would maintain agency with any action the player takes. I would describe the consequences of their choice and ask what they wish to do.
"I search everything."This way the consequences for actions are known and the players can make an informed choice maintaining agency receiving the expected result from their actions. As a byproduct consequences for bypassing the Dungeon Master's carefully crafted rooms are maintained as well as the player not feeling as if they are having to jump through hoops.
"Ok, it will take you nine turns individually, or three turns as a group to thoroughly search "everything else". This will result in either three wandering monster checks if you search alone or one wandering monster check with a higher chance of a monster appearing due to the activity and noise if you search as a group. You may instead choose to specify what areas you are searching specifically to avoid having to do such an exhaustive search. What do you wish to do?"
"Using your example with the random encounters, if the player does say yes to the random encounters, do you just roll and then they discover the loose flagstone behind the throne even though they did not mention the throne at all, let alone behind the throne?
"That bugs me for some reason. I feel your method would speed play, but at the cost of actual discovery. I feel it would be more rewarding for a player to discover the loose flagstone if they thought to look behind the throne."The rules of the game indicate that there are two levels of hidden. "Concealed" and "Secret" so the answer to the question depends on what the hidden area is.
If it's concealed, then any verbal description of saying they are going to look at the area will discover it, as will any 'through search of the room' trading time for risk. If it's secret then searching the area gives the 1 in 6 (or 2 in 6 for elves, or 3 in 6 for Dwarves (sliding stone) given in your example) chance to discover.
It is more rewarding for them to search for it themselves. The risk of having an encounter should be a fairly serious threat, so if they want to search every room they will not make it far.
I think also, that this particular mechanic is vastly improved if you note that the detection of a room trap or a secret door does not in any way grant information on how to disarm the trap or open the door.