Not LIVE FROM THE MINNESOTA SEARCH SPRINT, but found on the plane ride home...
The {search_dataset} has a unique key named "sid_type". Because of the query in search_wipe, which is called on every single sid that gets indexed, this unique key should be an index.
    db_query("DELETE FROM {search_dataset} WHERE sid = %d AND type = '%s'", $sid, $type);
I think that this was an index at one time. And I think that this might of gotten mixed up in the conversion to schema api.
This patch should be backported to 6.x.