Channels not marking as read?

[MarcinnT]

There is a very peculiar issue that's been affecting our forums for quite some time now. For some users, the ‘Mark Channels Read’ button isn't marking any channels as Read, and some of the Channels appear as ‘Unread’ spontaneously, even if no new posts have been been made.

We tried changing a few things ourselves, and it seemed to take care of this problem, but it just started happening again. Here's the list of what we already tried:

Changed Marking type to Cookie based. I changed to cookies,and then back.
Changed Marking type to Database (no automatic forum marking)
Changed Marking type to Database (automatic forum marking)
Launched forum Maintenance
Cleared system cache
Updated to the latest version of vBulletin
Changed Cached Post Lifetime from 7 to 10 days

I'd really appreciate if you guys could help me out with this one. It's very annoying.

Thank you!