I was able to recreate this, but it was a CDN (edge cache) and/or browser cache in my configuration that was bypassing your query.
For the browser cache to be a problem, the searches had to occur as the result of a link click. For example, if you clicked a link to ?s=term, it would check the browser cache first. If this occurred as the result of a form GET then it should bypass the browser cache, but I may be wrong about that.
To test this: check your .htaccess file for caching rules. Go Daddy uses browser caching rules to improve performance and compatibility with CDNs.
For the CDN / edge cache to be a problem, you would have to be a visitor (no cookies). CDNs cache pages along with meta information (i.e. how the page “varies”) and this is usually the user agent, language, and some other things.
Go Daddy’s ultimate hosting plans come with a CDN feature (which is what I tested with), but this may also happen with cloudflare or another CDN, too.
To test this: Visit your site in a different browser or modify your hosts file to use your hosting server’s IP address instead of your CDN’s ip address.
For a solution, I personally recommend using ajax. You cannot prevent some layer from caching the rendered HTML output of a search page, but you can embed an ajax callback to log the search string.
I hope this helps!