Are you using third-party cookies? MSIE could be configured to block third party cookies from sites without P3P. These days, most IT pros don't consider P3P to be sufficient authentication to accept third party cookies, and not all browsers have P3P support anymore.
I'm not aware of MSIE 6 flat out blocking a site if it didn't have a P3P statement. (Your mileage may vary.) I've never used it for anything besides 3rd party cookie management.
I was going through the documentation for the latest version of our shopping cart and it recommended implementing P3P. I had remembered reading about it years ago, but my memory was hazy as to why we didn't implement it back then. Thanks for the info, timster.