I'd like to draw your attention to two significant (and possibly related) search module bugs that are leading to widespread corruption of our search indexes:
Missing nodes in search index:
http://drupal.org/node/139537
The problem is missing content. You can't find a node with the search index if it doesn't get indexed for some reason.
Duplicate entries:
http://drupal.org/node/143160
The problem is duplicated entries in the search index which bloats the index and makes potential upcoming query optimizations impossible.
Neither of these have been diagnosed and the source of the bugs have not been identified. If anyone is interested in the search code (and there is a LOT of cool stuff in there, very well worth looking at) is invited to jump in and help us out with these efforts.
-Robert