As Tom mentioned above, vBulletin has a hard time when forums get this big. While there have been really drastic improvements in scalability, it's not perfect. You're above problems are due to this scalability issue.
In a perfect world, every time you view a thread it would mark in the database that you've read it. Then, when you load a forum, it knows without doubt which ones you've read and which ones you haven't. On smaller forums, this is not too taxing of a task and that's how it functions.
When the board gets bigger, this becomes harder and harder to do. Instead, there are different options to determine which ones you've read and which you haven't. While none of them are perfect, they're more efficient for the system, and with a forum this large the most accurate options aren't possible.
The scaling problems in this particular site are two fold... not only does it have a lot of posts, but the rate at which new posts are added is very high as well. This complicates the issues. vBulletin is very dedicated in solving these problems and I'm confident that things will improve before they get worse. These are simply new hurdles; 10 years ago, there weren't forums with 10M+ posts.