I've actually switched to Yahoo search in the last 3 months and find it better than Google, it definitely seems to be updated more frequently and the results are always as good, and sometimes better, than what I get at Google. There ads aren't as well targeted apparently but I never click on Google ads either so I don't really notice.
I think more than anything Yahoo needs a brand refresh. Like Ask did with the 'its the algorithm' commercials. I tried Ask based on those commercials, the problem is Ask doesn't have the quality results that Yahoo does.
With the new open search platform and support for microformats I think Yahoo is in a good technological position to take on Google, they just need better marketing.