I had a similar problem, I don't know if any of it rings a bell. My Seam app is running in a frame and when the host app was generating the URL that pointed to my app with getLocalAddr(), I was seeing similar ViewExpiredException even if my app just started. When the host app used getServerName(), finally everything worked fine. In the meantime it was no fun... I don't know if any of this applies to your case (frames, etc), but I hope it helps!
Thanks for your reply.
But this occur only in IE6 ?