Yes, that would have been a great way to do it as well. However, the most interesting aspect of the study to me was that they used Microsoft's methodology, comparable sample sizes, and examined the effect of changing search terms from Microsoft's "recommended" list to ones that study participants suggested themselves.
Incidentally, you don't need a giant sample to estimate the variance on the Google/Bing ratio -- you can use any number of resampling techniques like bootstrapping to get that estimate.
Good point - particularly as it's a fairly simple universe of answers. I wonder if we could get the raw data. But, I do think the Mechanical Turk vs "shopping mall" selection-bias factor overwhelms everything else.
I think the right thing to do is to conduct a much bigger study, get a much better estimate of the preference distribution, and then derive the % probability of getting a result at least as favorable as the Bing result by pure chance.
If you can show there's only e.g. a 1% chance that the Bing result arose through random variation, then Bing definitely has some tough questions to answer. (e.g. did they run 100 different studies, and just cherry-picked the best result).