The current code for drupal 5.18 (encountered the bug on) and 6.12 adds a ranking clause like so by default:
%d * POW(2, (GREATEST(n.created, n.changed, c.last_comment_timestamp) - %d) * 6.43e-8)
This is then used to calculate the final relevance of all nodes that were brought up in the search results. However, if there is no entry in node_comment_statistics for a given node, c.last_comment_timestamp will = NULL. In both the versions of mysql I tested with GREATEST(any number, NULL) will return NULL; subtraction with NULL returns NULL; multiplication with NULL returns NULL. Finally, the relevance is returned as NULL.
The attached patch is against drupal 5. Drupal 6 has MAX(c.last_comment_timestamp), and MAX(NULL) is also NULL. So, the patch to drupal 6 could simply be MAX(c.last_comment_timestamp) || 1 (or some such low number). Something simily might need to be applied in the 'status' switch in node_search in drupal 5, but I'll leave that up to someone who knows the code better.
FAILED: [[SimpleTest]]: [MySQL] Unable to apply patch 488166-fix-reroll.patch.
FAILED: [[SimpleTest]]: [MySQL] Unable to apply patch 488166-fix-search-relevance-d6.19.patch.
FAILED: [[SimpleTest]]: [MySQL] Unable to apply patch 488166-fix-search-relevance-d6.16.patch.