Well, I answered my own question.
It seems that our jforum_sessions table wasn't getting updated properly and therefor causing strange results for the "new messages" icon on the forums and topics pages.
I originally thought this table should be deleting people's session data when they log out, although, now I understand that it is used for figuring out the person's last visit which is tied to all the bells and whistles. Make sure your jforum_sessions table is updating properly for the forums to make sense.
[originally posted on jforum.net by coolbreeze]