Unfortunately, I don't remember which addresses I was having this problem with, or I could ask you to see if they display the same for you. I don't think it's related to cookies as they are already set to be deleted upon closing the browser, which I do multiple times a day. Most of the time, I'm not logged into a Google account either, so unless they are tracking me by IP # or something else, it shouldn't be based on my search history. On most non-Google pages, I also keep Javascript disabled from Google domains.

Is this the FF containers you are talking about?:
https://addons.mozilla.org/en-US/firefox/addon/multi-account-containers/
(Or are you using FF nightly - that page says it is built into that version)
I haven't tried containers before, and it looks useful, but I do pretty much the same thing using different browsers and different browser profiles for certain sites.