It turns out that this new behaviour is, in fact, a feature - Opera remembers the content of all the pages you've been to as well as just their URLs, and then it tries to give you the most relevant matches in your address bar. Well that doesn't work for me. Address bars are for typing addresses and search engines are for searching content in my world, maybe I'll find this useful one day but that day isn't right now. The good news is, its easy to turn off.
Just go to Preferences -> Advanced -> History and then uncheck the box "Remember Content on Visited Pages". Now when I start typing, I just get the URLs that look like my actual words, and with the shortest matches first. I'm safe to upgrade the other machines now!