I'm actually not that surprised. We issued a press release today on a search engine study our company had undertaken. Over the last couple of months we'd seen a major shift in the relevancy rankings at MSN. They are far better than they were just 12 months ago. Factor that in with freshness of content and voila! you've got a pretty darn good search engine.
I honestly think the sandbox is hurting google, and the lack of indexing on a regular basis is going to hurt Yahoo and Ask.com. If a new restaurant opens up in your town and launches a web site, and you rely on Google for all of your searches, it may be a year before you see it.