Microsoft's new search engine, called Live Search, looks pretty good at first glance. It looks almost exactly like Google, which is probably a wise strategy. Many of the other search engines have interfaces that are quite different, and probably put some people off with all the options and choices. I tried a few test queries and compared them to what I get on Google, and Live Search appears to do a very good job of cutting down on non-relevant results. It also seems to do a good job at finding the most likely "best fit" items, which are usually what you want to see on the first page. Finally, the system also seems to be making an strong effort to index blogs; I found several items in search results that pointed to blogs that I had not seen on other search engines.
And of course, it has ads that also look just like Google's. If any company has a chance of unseating Google as the king of search, it is Microsoft, and it looks like they learned some lessons from their earlier attempts at search.