I don't use a Google Toolbar and have the same problem.

In the UK you can turn this off by clicking on Preferences, to the right of the search box, and then selecting 'Do not provide query suggestion in the search box'

Hopefully it should work for you too