Hi,
Thank you very much for the details, it helps us a lot. The issue seems to be completely random, it indeed happens sometimes, other times does not. That means, that the problem is not plugin, but server related – as programmatical issues can be replicated a 100% of the time with the same input parameters, and here it is not the case.
I have seen this exact issue about 3 times, and in 2 cases it was the PHP memory limit. Basically as you expand your site, add more plugins, or plugins update, codes change, the memory consumtion will change, and if PHP was almost out of memory per thread, some requests may result in failure.
I recommend increasing your PHP memory limit to 512M at least, to see if anything changes.
In the remaining one case, there was a hosting issue – the hosting server was on a very bloated shared environment (I don’t recall which, bug either godaddy or siteground), and there was a limit of concurrent request for the server in a short time window, so some of the search request basically were ignored.
I hope this helps!