Although an Autocomplete question was asked last year, I wanted to see if there was a solution that worked in both IE and FF that disabled the Google Toolbar Autocomplete.
A Google employee suggested they will release support for the autocomplete="false" attribute, but it appears it will just be for FF.
Update: - I haven't found a solution to this problem, the autocomplete="false" doesn't work in the current version of the toolbar.