Security token/cache issue

[t325]

I posted this on the official vB support forum, but I'm not getting anywhere over there with this issue, so I'm hoping you can help me out.

We've been having a lot of weird issues on our forum, a lot of them revolving around security tokens.

When some, not all, members post, they get the security token issue. They also only get it in certain threads and forums, for example, one member couldn't post in one forum, but he was able to post in another.

Another weird issue one of our moderators is having is getting into the mod CP. When he logs in, it will keep looping him to the login screen. But, if he hits refresh, it'll load up the mod cp.

Another member said new posts in a thread don't show up until she posts in that thread.

I searched about security tokens and found all of the solutions posted thus far. I don't think mods or the skin are a problem because:
1. We've been running 3.7.0 since it was in RC and never had any problems until now
2. Problems are happening with the default skin which has no changes made
3. Our custom skins are pretty much just CSS and image edits, with a couple minor changes (nothing that would affect forms, just layout) in a few templates
4. I disabled all addons and the problem persists

It seems to me like the issue has something to do with the user's cache, although the ones who I have asked to clear their cache said they did and it didn't fix it.

I'm also 99.9% sure that I know where the problem lies, just not how to fix it. I upgraded our server from PHP4 to PHP5 and that's when the problems started happening. So, I'm almost positive that's the problem, now I just need some pointers on what might be wrong and how to fix it.

Again, to reiterate, this is happening with ALL mods disabled and a fresh copy of the default skin. So please don't post a link to that thread on the vB forums and consider this resolved, because I've been there, done that. The issue seems to stem from some sort of cache somewhere, likely some server-side caching I don't know about because the users are clearing their cache and have never had this problem before upgrading to PHP 5.