Reported to me by Mindless. Appears to be happening more often than not, but not 100% of the time.
Only done some very quick investigating so far (basically confirming the issue does exist, and confirming that just rebooting the server + applying latest PHP/etc updates doesn't fix it).
Search has always been a tad slow, so I suspect this may be a matter of that the site's database has grown so large that timeouts are occurring when trying to search it. Solution might just be to increase the timeout cutoff.
Workarounds in the meantime:
1. After getting the error, try refreshing the page (click "Yes" to resubmit info if your browser prompts). It may work the second time.
2. Or, use Google or another search engine that lets you filter by site.