Another possibility is that you use some rare static IP, which Criteo could somehow connect to email. But it's probably a stretch.
Keep in mind also that some of your correspondents could agree to share their email list on some site or to some app, so that could leak the email itself and real name (but still it's unclear how it was connected to your browser).
Here is the note on the bottom of the email from Tradesy/Criteo:
To opt-out of receiving Tradesy emails, click here. This message is personalized by Criteo Email based on your previous browsing behavior. To understand why you received this email and access Criteo Email privacy policy, click here. If you want to opt-out only from Criteo Email personalized emails, click here.
When I went to their email privacy policy, it doesn't explain how they got my email address.
I am very disturbed by this kind of stealth data mining. Is there a way to set up my browser to become more anonymous on the internet? Clearly my ghostery and ad block is not effective. I deleted my Facebook and Linked in after Linked in somehow spammed me to link contacts that I sold random crap to on craigslist (and probably spammed them too.) Somehow they both still deposit cookies. I am willing to pay someone who is familiar with this landscape to block trackers from invading my internetting. Or block websites that use criteo and similar. Is this possible?
I'm not one of those people that wants to go "off the grid". I use credit cards, I use amazon, I know what I'm getting into. It just seems like Criteo has crossed a line.
Are you sure you don't have some shady/little-known extension/plugin/app? Those can share browsing history with advertisers. Some freeware firewalls/antiviruses can too (just googled an example: "AVG, the Czech antivirus company, has announced a new privacy policy in which it boldly and openly admits it will collect user details and sell them to online advertisers for the purpose of continuing to fund its freemium-based products. This new privacy policy is slated to come into effect starting October 15.").
Maybe try to communicate with someone from Criteo (not support, but somebody higher) and describe your weird case?
Theoretical possibility then:
You still use that personal email in the same browser? That means you visit Yahoo website, which can set some cookies identifying you, including third-party ones (advertising/tracking), if those are not blocked by Safari. The same tracking cookies can be used by Tradesy, so that site can tie your visit to your Yahoo identity.
I actually use the Apple mail client, so I get my spam mail and my personal mail in the same interface. My angry deleting of cookies and web history following the Criteo email would have cleared any log ins, but I haven't used the yahoo mail web interface for many years. However!! I remember going to flickr briefly about a month ago, and since it is a yahoo service, it would have been connected to my personal yahoo ID/email address (correct?). It's possible that I never logged out, so could it have mined my address that way? I am still incredulous and outraged that Criteo could use this to mine my address and spam me, but this could be how they got my personal email/yahoo ID.
Thank you so much for your insightful comments and for "investigating" with me! Even though this is still somewhat mysterious, I've learned from this and also discovered my ghostery settings were off which was very valuable. Now I just have to figure out how to block Criteo and similar invasive species. I may have to go off the grid after all.