I wouldn't say there is a trivial fix. One option would be to encrypt the search term client-side with blowfish (or some other 2-way hash scheme) and use that as the url string.
But as for a fix, at least Opera offers the option of never sending referrer information. That would be enough in this case.