Help!

We have a new website that's had the usual startup teething pains. The biggest is cookie rejection, especially by IE 6. We thought we'd resolved this by instituting P3P and it has helped a lot. However, we have one client on IE 6 who still shows signs of cookie rejection: He reports that the View / Privacy Report shows our cookies are accepted, but still our server code (php) loses his session context between pages.

I've gone through his browser settings with him over the phone, and there's no obvious problem. His privacy setting is medium-high (even going down to 'Accept All Cookies' doesn't help). It gives every appearance of being a cookies problem, except that cookies seem to be fully accepted by his browser.

Strangely, this client had no problems with our system a few weeks ago. He's coming in from a new IP address recently but I'm not sure how that could cause this problem. Obviously something has changed, but I'm stumped.

Any ideas?