An easy way to tell for sure would be to look at the status bar of the IE 6 browser. At the bottom towards the right there would be an "eye" icon with an exclamation point (or something similar) indicating privacy measures were taken with that site. You should be able to get details by clicking on it.
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.