I was able to make the evil eye go away by simply adding this small header to the site in the IFrame (PHP solution):
header('P3P: CP="NOI ADM DEV COM NAV OUR STP"');
Remember to press ctrl+F5 to reload your site or Explorer may still show the evil eye, despite the fact that it's working fine. This is probably the main reason why I had so many problems getting it to work.
I found a nice blog entry that explains the problem with cookies in IFrames. It also has a quick fix in C# code:
Frames, ASPX Pages and Rejected Cookies
I must admit that I dont really care what it means, I just needed stuff to work in Explorer. The sites are our own non-public sites one of which uses a cookie to 'remember' which style to show the site in. So, yes, I just mixed tags until the evil eye disappeared.
The increasing irrelevance of P3P. cylab.cmu.edu/files/pdfs/tech_reports/CMUCyLab10014.pdf If it's so legally binding, there'd be lawsuit precedence by now proving such. It's viewed with such high esteem that all but one of my competitors even bother posting one in the first place. They must figure that if their customers can't leave the IE setting on Medium, they aren't worth the effort. Sales lost on one site would have to be pretty high if cookies don't work, the cart dies without them.
This answer suggests using a dummy header like CP="This_is_not_a_privacy_policy". Doing that seems less legally binding, I think (since e.g. NOI and STP and nothing like that at all is mentioned), and apparently makes IE happy :-)