Hmm, you do have a P3P policy on your website yet it's not working? Review your policies. Does it change behavior depending upon your browser or is it more of a "is someone picking their nose in Cleveland right now" sort of deal? Of course, the browser's acceptance of the cookie entirely depends upon how their settings work versus the browser's P3P policy. It's possible that the browser's P3P policy won't accept any of your cookies in which case you need to come up with a different way of sending session information. I can't tell you more without more specifics but this should at least get you started. You can learn more about P3P here, here, and here. Here is a free P3P policy editor to make certain you don't miss anything.

Of course, you may also want to check whether or not your script is properly setting the headers. For this, I would direct you to Mozilla's Firebird. Install that and check out the extensions, specifically Live HTTP headers and Web Developer. These tools have helped me greatly in the past.

Sorry this was so long-winded. I hope this helps you with your problem.