Can Yahoo beat Google? All I can say is that the potential is certainly there, because no current search engine is even close to perfect. There is much room for improvement, and anybody who makes a significant step up in search quality will gain huge market share.
In our current eyetracking project , we have been watching hundreds of users doing thousands of searches on all the three main search engines. Of course, it's not my job to help the search engines - I aim to discover exactly how users look at search listings so that we can tell our conference audience how to write better page titles and content on their sites.
Still, we have recorded thousands of cases of users clicking though to sites that didn't help them - all opportunities for improving search quality. The quality criterion is not "relevancy" in the abstract. As search engines have become answer engines, search quality equates to task performance : do people find sites where it's easy for them to pick out the info they need?
To measure search quality, perform usability studies where users are given typical tasks to perform. (One we tested is how to tie a certain type of knot, which is also good for giving us eyetrack info on how people look at animations, since some sites demo the procedure with animations whereas others use a sequence of drawings.) Then score the search engine for how often users perform the task right (plus other usability metrics like time on task and user satisfaction).
In my example, many of the highest-ranking sites make users tie the knot wrong, so that it doesn't hold up in use. A better search engine would point users primarily to sites with easier-to-understand content.