I suppose the algorithm doesn't randomly try to insert strings into the search box.
Actually, Googlebot has done so and may still be doing it as I've not head to the contrary.
but I also don't think someone would link to these pages.
Who knows what people really do... there are weirdos out there! :-)
But could there be other reasons?
Yes. Actually Googlebot is not alone. There are thousands of spiders checking out websites and once in a while one of these may index your pages somewhere which is found by Googlebot and then checked out... and then indexed.
Also, Google themselves have had an experimental bot which would add sub-folders on one of my websites. It would end up with something like:
Because my CMS shows
/foo and ignores the children, it would actually return a page. The good thing, though, is that the CMS would properly define the canonical URL so I was never penalized because of that bug. But I had many like that for a while... Hackers can also end up generating some mostly random URLs so it could look like a search even if it isn't a real search at all (i.e. the Google searches use a GET so whether it came from their form or not is not relevant to the shown results.)
As mentioned by Trebor, a good idea is to put all the results under a folder such as
/search and have that path forbidden in your
That will not prevent those hackers from making your search pages public, but it will not impact your search results since Googlebot will ignore those links.