Yes, that doesn't work either. From what I understand, the domain parameter on the setcookie function only applies to subdomains of the current domain. It seems there is no way to set a cookie for another domain even if you redirect to that domain, in the same script that you redirect in that is. Of course, the page redirected to could set the cookie, but that won't help me.
I think I'm just going to redirect with a url parameter and check the user agent and redirect spiders to a version without the parameter.