Everyone in our shop has the same problem.
You can search one term and get no results, then try the exact same search again and get results.
Same with moving to the next page in a multipage (like "page 2 of 233") result set. It is quite random if your "next page" request will return no results.
Using google to search usually leads to broken links
Please fix it soon!