Can be an IE problem with cookies, there are a couple of ways round this with IE. Look at the P3P policies available on the W3C website, or use the propogated PHPSESSID if using sessions in the URL.
Admittedly the latter option is a potential security hole, but without cookies, then personalisation of sites can be difficult.
Another way I suppose is to continually pass a variable around in a form, but anyone who knows what they are doing will be able to find this "key"...