There is one bug that might relate your problem which I ran across, which I reported to Lincoln Stein but I don't know if he fixed.

If you look in the source code to CGI::Cookie you will find a comment about Netscape sometimes sending a double cookie, with the first one being the right one. With IE 6, sometimes, I found that it would send a double cookie and the last one was right. Change ||= on the line following to = and see if that fixes IE 6 for you. (It will break old Netscapes, unless you want to do a browser detect, you can't reconcile the two behaviours.)

No, I don't remember the exact circumstances that cause this misbehaviour, just that I looked at the behaviour, fixed my copy, and reported the bug. And Lincoln didn't seem convinced of the need for the change, but I was swamped and didn't follow up properly.