Ever since the last quarter of 2007, SEOs and Webmasters have been complaining about not being indexed in Live Search. In short, many sites that were once indexed and ranking in Live Search were no longer. Plus, many new sites that one would have thought would be indexed and rank well in Live Search, were not.
An updated WebmasterWorld thread reportedly has a note from a Microsoft representative (note, this may be removed soon, so trust me it was posted). Here is a quote from a member named "nickreynolds."
The Live Search team is in the process of modifying the algorithms we use to determine which sites are indexed by Live Search index and which sites receive a ranking so our crawlers will visit the site. At the end of September we launched new ranking and indexing algorithms that were stricter than we anticipated, and we are now changing them to bring back many sites that were removed from our index or given a lower rank. We apologize that it is taking so long to remedy this situation, and we are treating it very seriously. Having high quality content is important to us and we want to make sure we get this right.
We do not have an exact date for fixing this issue, but our plan is to have it resolved near the end of spring. This is our number one priority and we have put all our resources into solving it and bringing a better balance to our indexing so it won't happen again. We appreciate your patience while we resolve this issue, and hope you understand that at this time there is nothing we can do to modify or improve your site's index or ranking.
So as you can see, Microsoft admits their Live Search September 2007 update caused many sites to get deindexed from Live Search. The new update, which I believe we have seen signs of a couple weeks ago, should bring back many of the sites that were impacted by this "stricter algorithm." Of course, we do not have an exact date of when this new update will go live, but as I said above, on February 6th, many Webmasters reported a small Live Search update, which seems to have died down. It may have been some quick tests by the Microsoft Live Search team.
Forum discussion at WebmasterWorld.