This problem has been reported in several forms, but the problem is this: after clearing all history, cache, etc., on typing 3 characters the autocomplete will reveal a site that has been accessed in the past. Nothing seems to clear those autocompletes.

I discovered the solution (after 3 years) today.

For those of us (including me) who do not use Opera all the time, you have seen the term "Speed dial" but you weren't sure what it was. Well, it's those tiles you see when you are on a "blank" page/home. There are two rows of tiles with sites that are put there by Opera (probably for a fee) as well as some you add on your own or in some way by accident. If you type the first 3 characters of any of the sites you added (perhaps by accident - I am not sure how the one I had was added), the site will autocomplete. Delete the tile and it will stop autocompleting.

Finally, after 3 years! Let me know if this helped you!