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?