Here's the first test I use to decide whether a search engine (that is relevancy based like Google, Yahoo, MSN, or Ask) deserves praise over Google: put in my last name and see if it ranks that properly. Why does that matter? Cause I have thousands of inbound links.
It set me thinking about how one decides how good a search engine is. I suppose the ultimate test would be the extent to which, over time, the right information was delivered when searched for. However, even that test is flawed because there would be an element of the user changing to fit the search engine as well as the sheer impracticality of comparing search engines that way.
One way that might work better is to come up with some program that automatically searches search engines for a specific information, when it already knows what that information is. Essentially what Scoble's doing. But then there's another problem. There are two possible types of webpage wanted when the search string 'scoble' is typed in. Not only Scoble's site, but possibly also the site that has the best and most reliable information on Scoble. It's just an example, but I think the point clear.
Probably the future of effective search lies in not only ranking the pages, which is what Google is good at, but in working out what the pages mean and what type of information the user is looking for, over and above the search string. The ability to test search results reliably is the only way that search engines can improve, and the winner of the quest to test the best may well also be the one that finally beats Google, unless Google get there first, of course.