I think you're missing that setting cookies alone isn't what allowed evil.com to sync identities. They needed to set the cookie from one site, and receive that same cookie when the user visited a different site.
With CNAME cloaking, it's true that EvilCo can set cookies on both evil.foo.com and evil.bar.com. But when a user is on evil.foo.com, there's no way to make a request to evil.bar.com that includes evil.bar.com's cookies. This is the mechanism that stops syncing identities.
Does that help?