Believe it or not, I've seen this problem before. I know that IE6 does not like *some* special characters (not sure about the complete list of problematic characters) in the sub domain name portion of the URL such as underscores, etc.
What is the sub domain part of your URL? For example, I've experienced IE dropping and/or mishandling cookies with URLs like this:
Note the underscore. I know it causes a problem for IE6. As I recall, it was especially a problem with HTTPS URLS. Obviously, URLS should conform to the RFC guidelines.
Is there any way around this? Issue? Or is it just the case that IE6/7 won't handle cookies for domains (subdomains) with underscores?