I've never had a problem with the Take10 and Take20 rules. As I see it, they're just quick ways to handle a character doing relatively routine things quickly, without stopping for a die roll.
In the case of Taking10 the character just does an average job, quite useful for things done routinely. In the case of a game I'm running, the scout checks the way ahead with a cursory search in each area of the corridor, taking10 on his search roll. It enables me, as DM to judge whether or not he finds some basic corridor traps without the player having to roll every 5' square.
In the case of Taking20, it's just the PC spending time and doing the best job the PC can do... which says little about whether or not the job is actually doable by the PC. The search DC might still be too high for the PC taking 20 to achieve. So it's not really a case of the DM just saying that the PCs search until they succeed. Getting a 20 on a skill check does not mean they succeed. It just means they do the best they can do.
I think it's also important to stress how much time it does take compared to rolling a single die on a single check. I've given the PCs situations in which taking 20 was not really possible given the time constraints they were under (not without being discovered and attacked by alert guards, anyway) so they had to resort to basing their hastier search rolls on the clues I gave them from the room description.
As far as whether or not searching requires manipulating/moving things, I assume it does in some cases. If there's something hidden in a bed, they'll most likely have to touch or move the bed to get at it. The relative success of their search check indicates whether or not their PC thought to move the bed. If they succeed at the roll, obviously they did so. If they took 20, I also think that makes it obvious they did so as well. But what I also assume is that the touching is done after first eyeballing the situation and that any movement is done carefully. Therefore, I don't assume they automatically trip the trap that is triggered by moving the mattress by conducting their search. If their search check had been enough to detect the trap, I assume their search found the trap before triggering it, thus putting the moving of the mattress on hold until the trap is dealt with. As a result, I'm pretty much assuming that traps are to be found before anything else, given a good search result.
Given the way I do things, I don't really see a problem with taking 20 on searches. It's not auto-success. It's not an insta-find, except in the way it is adjudicated. The PCs still spend the time, which can have consequences (certainly for spell duration expiration if nothing else).
I can see the OP point that taking 10 on a task like climbing can lead to weird appearances of success vs failure. And the character on the less successful end of things has to be made subject to risks the PC with one more point of the skill is not subject to. If that PC with the +9 on his climb must roll to make the DC 20 climb check, he might miss by more than 5 and fall, something the PC with +10 on his climb is not subject to due to the Taking10 shortcut. But I still think taking 10 has a positive use here. At some point, a PC is skilled enough at something that it's not really worth making a check for certain kinds of tasks. I'm content with it coming down to a difference of 1 point in skill modifiers, in part, because the better skilled PC can always Aid Another to extend that 1 point difference into auto-success on taking10 for other PCs with similar skill levels. Other PCs will still have trouble even with the help, but that just serves to illustrate that they're that much farther behind the more skilled PC anyway and shouldn't be given the same benefit of the doubt he's given when it comes to accomplishing tasks he's well skilled in.
I guess that's a bit of a ramble but that helps outline my philosophy on why taking10 and taking20 aren't bad.