This sort of problem is almost always related to the tcthread_lastview cookie. It's been an ongoing issue with vBulletin for years -- a known issue -- that they seem to constantly rewrite their cookie handling to fix, but always just find new ways to have it broken because they're ignoring a fact of life with browser cookies -- a maximum size.
People who read a lot of threads and rarely close down every browser window they have open are the ones most likely to encounter this problem. The problem is that over time the tcthread_lastview cookie is appended with the thread ID and last read date/time of every thread you read in the forum. When the cookie reaches its maximum length, nothing is ever done by vBulletin to deal with it -- it just keeps trying to append to the cookie each time you read a thread. But now, only threads you've already read will behave properly because any new thread you read gets appended (and truncated), but any old thread you read that's already in the cookie is just updated and continues to behave properly.
If you use Firefox, you can just delete the offending cookie when it starts happening.
A simple fix/workaround would be for vBulletin's cookie update code for tcthread_lastview be modified so that if it sees the length of the cookie is beyond a certain size, it prunes out info on older threads. Or it could just be modified to prepend new thread info and updated thread info to the cookie and older stuff automatically just falls off the end when it reaches the max length.
A more proper fix would be to store this data server-side where there aren't such limitations. There is a max length client-side per cookie as well as a max number of cookies per site so any other solution only changes where the problem is encountered rather than fixes it for good.