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.
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.