I have rebuilt the search index and contacted the host (the last time I brought this up). The host says they can't see anything that would prevent the search from returning all of the results.
But let's just say that there is a setting limiting the number of returns, that still doesn't explain the sporadic omission of newer results that would fall below the setting limit.
I'll send another ticket to the host and see if someone else spots something on their end