Thanks w-e-v,
At least it you have narrowed it down to cookies.

Being a random/intermittent issue does make it harder to work out why this happens.
Does this appear to be browser specific or does it happen with any browser?
Do you have any 3rd party extensions that could possible alter the way cookies behave?
Thanks.