Are you using PHP 4's sessions?
Are cookies being allowed on the browser?
Are you running any cookie-blockers?
Out of interest, if you change location to refresh, does that make a difference?
Having said that, you are pressing BACK. The browser may well be using a local image (somehow) of the page, or one of the servers along the route is caching it.
During the Logout bit, do you clear out the cookie? You may want to set it to LOGGED_OUT and test that too.
Not sure.
I am using the headers like you and if I press back, I get an expired message (as I expect to get).
Richard.