Drupal 6 - Core Search Module Not Indexing Node Titles
I was able to fix this issue by changing the Indexing throttle setting for Number of items to index per cron run from 100 down to 10. 

Once reindexing was complete all node titles appear to be indexed and appearing in search.