Google says, sometimes Googlebot may submit GET forms.
Specifically, when we encounter a element on a high-quality site, we might choose to do a small number of queries using the form. For text boxes, our computers automatically choose words from the site that has the form; for select menus, check boxes, and radio buttons on the form, we choose from among the values of the HTML. Having chosen the values for each input, we generate and then try to crawl URLs that correspond to a possible query a user may have made.
I think it's much more probably that it's some rogue spam bot than a bot from a reputable company like Google.
How about simply logging the IP and user agent when an user enter such a query?
This was happening on my site and as it turned out when the user hit enter on the keyboard in an alternate textbox, like for quantity, the search fired. While it could be a bot, I'd think this scenario is more likely.
To test, try hitting the enter key in alternate fields besides the search box.
This is totally unquantified, but I have seen cases where fairly obscure search results pages for a couple of my sites are showing up in Google's index.
While it's possible that this is due to them inserting random strings, I suspect that these URLs are coming from other places, either the Google Toolbar, or from Analytics where I have configured it to understand my site search URL pattern.
Users are able to use the search feature of most sites right within chrome.
In Chrome, type the domain of a site, then press tab and you will be prompted to input search text. This search uses what google is assuming is the search form of your site. I believe this maybe the issue you're experiencing.
Ironically I've got a similar issue myself, our site has a 'dealer lookup' form which Chrome is using, instead of our 'site search' form.