The only possible scenario I can think of that would do this even if the cookie is deleted if the browser, for some reason, is reloading the page completely from cache and not requesting a new one from the server.
Why it would do that, I have no idea, however it's worth a shot to compeletely clear the temporary internet files and see if that forces it to reload.
