If that isn't it, I have no ideas. If these are stock IE 6 browsers, and they're getting the page to come up OK, and the cookie isn't being generated from a different web site name (doesn't have to be 3rd-party like on a different domain, just a different system), I have no explanation. I have never seen that before.
I might suggest you get some low-level debugging in there logging what cookies it's sending to the browser and recording what the browser sends back. The hostnames of the systems they're using might be nice, just to verify.
I suspect one of your assumptions may be faulty here. Test them all.