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, comp

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.