1. They should've deleted _all_ relevant cookies (in the browser, as well as in the browsers cookie database)
2. There are many 3rd party companies that sell data packs that derive residential IPs from VPN IPs (we use some at work). A trusted/good VPN is a must
3. They probably came via the same User Agent (didn't mention changing browsers)
IP + Cookie + User Agent = Fingerprint (not a good one, but will work for Facebook's needs)