Tracking each message or thread for a user is resource intensive, agreed.
What logic do the Usenet readers use? The older ones were able to keep track of read/unread threads and messages, without all the fancy flags, and such.
I think they used "ranges" kept in the local ini file. Perhaps looking at that logic could lead to some better solutions.
This would be an extension of a user profile manager, and could either keep the profile information in a MySQL text field, or in a USERID.txt file that was updated once the user session expired. (though there is probably no advantage to that over a mysql text field).
You could expire this information every x-days (30,60, 90) if it hasn't been updated, depending on how active your forum is, and just keep the last_logon_date, or a system default of 30-days max (or similar) as the "new" period for a user.
This would in some ways be a side-ways look at a 'favorite' or 'watched' threads profile.
As interactivity becomes more important, especially on support type boards, the ability to mark messages read/unread and threads read/unread or 'watch' becomes important.
Creating an entry for user and each message is wasteful. There has to be some sparse-array or table logic algorithms out there to help with the problem.
Perhaps tracking up to 30 days of threads/messages and keeping track of what was 'read' and assuming everything else was unread would work for most people most of the time.