Immediately after they get logged out - the very instant, I mean, before visiting ANY other pages, have them visit this:
http://www.freaksforum.com/cgi-bin/ultimatebb.cgi?ubb=dumpcookies They should see between zero and four cookies.
If they see "login" and "session" then their new post notification cookies are working fine.
If they see "PnTf" then their Recent Visitors cookie is also working fine.
If they see "ubber" then they're not actually logged out.
Ask them to try different browsers. If using IE, try Firefox. If using Firefox, try Opera. Etc.
If the logout issue only happens when using one browser, then it's the browser (and the cookies it's storing) that are at fault.