I had the similar thing... try doing a cookie check on the landing check and if no cookies, prompt them to look at their privacy settings, and allow all from that particular site.
This is purely a client side thing with the P3P settings of IE6 I believe, and there might well be a workaround for it by providing the right settings for it - look at the W3C site - I am sure they have bits on it. Also look at the MSDN site for P3P settings...