[eluser]Maglok[/eluser]
Bargainph is right, IE8 is much stricter with cookies. Timestamp is very important.
You say it randomly shows a message, computers are by definition not really random so there has to be a pattern there.
You could try to set your cookie to last for, lets say, several years and see if it appears as well. If it doesn't it must be some kind of de-sync of servertime and localtime. If it does, then its interesting.