Unlearning is a great option. I have in Firefox a persistent autocompletion for a URL that I typo'd once, which still shows before the one I've been to a thousand times (because it's first alphabetically, I suppose?)
Even with search autocomplete disabled it takes forever just to search the history.