They cannot be setting a cookie for your domain. Some request to your site has to set that cookie.

Checking through your logs of what sets the cookies for anything suspicious you can then investigate further should be fairly easy, and contain the referring url of wherever page your cookie setting code was served on.

There's no easy technical solution to solving this other than telling them not to, or removing the partners that aren't playing by the rules.