Ich überlege, wie sie rausfinden könnten, was zu einem paßt, ohne etwas über ihn zu wissen und die History wäre etwas

Sonst haben sie noch Infos wenn man z.B. in Seiten eingebettete Videos angesehen hat, da wissen ja, von welcher Seite man kommt. Und das allgemeine Tracking Cookie hätten sich auch noch, falls irgendwo ein Analytics Cookie akzeptiert wurde.
Bist Du vielleicht über TOR oder VPN gebrowst und hast die Cookies/Storage nicht gelöscht?

Denn das sind doch sehr spezielle Empfehlungen, die Du bekommen hast.

Ich verwende SDC https://addons.mozilla.org/de/firefox/addon/self-destructing-cookies/ das löscht nach dem Verlassen eine Site die Cookies und den Local Storage.
Und denn EFF Privacy Badger https://www.eff.org/de/node/73969

Zusätzlich wird alles bei jedem Browserbeenden gelöscht.