I think the "marking old threads as new" was intended as a feature rather than a problem (at least according to a post I read a while ago on the YaBB forum.)
At the moment, when you view the message index, YaBB has to load the users log, then check to see if each message is new or has been read, then check to see if the forum or board has been marked as read.
When you view a thread, the information in the log file has to be updated. This means reading in all the entries again, and modifying or adding an entry for the thread being viewed, then saving the new information.
If you have a lot of enties in the users log, lots of users, and lots of threads, all this reading and writing will take time.
Compression may not help in these circumstances because everytime someone views a thread, you would have to load the users log, uncompress it, update the details, re-compress it then save it back to the server. You may gain speed in the read-write stages at the expence of processor usage in the compress-uncompress stages.
I really don't know enough about it to know for sure. You could try asking
Michael Prager who I believe has tried using Gzip compression on this board, but I'm not sure how it was implimented.