[eluser]jedd[/eluser]
Please .. call me jedd.
And a smidgen, yes.
Is this IE6 perchance? Famous for being predictably unpredictable.
It sounds like your security system is failing-unsafe. It'd be interesting to see your logout code - where you destruct your session data that is later used by your 'are we logged in?' function (also good to see that). It's possible that IE is remembering session data - I don't know what braindead features that browser had, but I have heard that it had many.
Have you tried hitting the web page from a DIFFERENT machine that has not used the site before, and using the same rev of IE? Being sure to not authenticate at all? That'd be the most conclusive test I think.