I'm pretty much whatever the circumstances would allow. How many of us misplace car keys, tear the house apart for them, call to the wife/roommate/whatever "Honey! Where are my **** keys!" and she comes over and picks the up straight away? Multiple rolls when you have plenty of time.
On the other hand, you're late for work and cant find your keys. You get one pass to tear the house apart and then you give up and catch the bus. One roll and you're out of luck if you miss it.
In this case, if it's necessary for the plot to continue, then the roll isn't to find the keys (the players will find the keys); the roll determines how long it takes. Failure just means it takes the maximum amount of time.
Now if time was that big of a factor, I don't have a problem with everyone rolling separately to see to finds the keys in the quickest amount of time, but it's not that important then just make it an assisted check.
Very true, and you can also use "Yes, but..." rules as well. Yes you climb the fence, but you are spotted by the Imperial troops.