Microsoft's previous search engines ( MSN Search and Live Search ), have suffered from a very slow and very small index. Now, unfortunately, Bing has followed suit. Although Bing has a lot of great and funky new features, the index size is still a problem.
Microsoft does seem to have a few tricks up their sleeves though. A new strategy which involves prettifying search results, and focusing on social networking, may just well be the answer to the changing state of the web.