I really fail to see how this is any different from rolling that 1 in 6 in earlier editions of D&D (or 2 in 6 if you're an elf). The mechanic has changed a little in format but the basic idea is the same. Why is the effect of 3E any different?
Plus, I'd probably assume that taking 20 would entail kicking through the straw since it is as thorough a search as the PCs are capable of. I think you had constructed the search in such a way that you were expecting the particular magic words "We move aside the straw" and the players didn't do that explicitly. The question I have is: Did they assume that by making a search roll (and taking 20), the PCs were doing just that?
The problem may be, partly, miscommunication with your players. They don't know what level of specificity you expect from them. Maybe you should consider giving them some examples if you haven't done so already or consider asking more leading questions to train them in the way you expect them to play.
For example, if I have PCs searching a room and rolling for it, I ask where in the room they are looking. After all, they might roll better looking in one spot where there's nothing to find and botch the roll elsewhere when there is something of interest. If they decide to take 20, I again ask them where. If they say the whole room, they get charged for the 2 minutes per 5' x 5' square for the whole room. And they had better hope they aren't under a time pressure.
With all the complaints about how players are now focusing so much on mechanics or looking at the game in a mechanistic or board game way, I wonder how many of you are actually doing something about it? Are you retraining the players to think differently about how to approach issues like searching under straw or interacting with specific objects in the room?
Personally, I encourage my players to think creatively about how they want to develop their characters, within the reasonable limits imposed by the availability of certain PrCs within the campaign. I make sure they know that they don't have to take a prestige class, they don't have to finish it if they take one, they don't have to get to the prestige class via only one route, and just because they take levels of fighter and bard, they don't have to refrain from stealing if they want to be a thief.