I have seen weird behavior like this before and we always solved it by completely resetting the browser back to default. It's a pain if you have a lot of custom settings, but give it a try and see if it helps. In IE go to Options > Advanced > Reset, close browser, then try again. You will lose all cookies, history, etc. I've seen this issue with every browser at least once, not just IE. If problems presist, reboot both your server and local client computers.
This works just fine, and it's what we've been doing, but I need something that I can do server side.
I'm hosting several ecommerce websites on this server and I can't have each customer coming to the site required to clear their cache/cookies/etc.
I agree it would be nice to find a server side solution (or any logical reasons this happens at all), but at least for me it has happened so rarely that I've never bothered to look. My hunch is that if you have a lot of complex applications and sessions, etc., things just go "bump" for no reason and cause cookie conflicts. Could also have to do with firewall settings, anti-virus, https, you name it. Systems in general are getting so complex these days I think it's inevitble. I would love to hear if anyone knows why they think this could happen.