4
I had the exact same problem. I found out that this happens because of that i use url redirection and some users had set their security level in Internet Explorer to middle, at this level Internet Explorer denies cookies that comes from another url than the one you have entered. If they instead used the "true" url everything worked perfectly.
I don't now if this is of any use to you but this was the root of my problem.