Ok, first of all. People all over the world have been using vBulletin 2 (which works just like PunBB) for years now and I have never ever seen anyone "complain" about it there. What's up?
There are known implementations, but they are all ugly. The most common implementation is storing the topics you've read in an array that is then serialized and saved in a cookie. I believe this is also the simplest way of doing it. There are issues though. How long should you wait before a topic is considered unread again? How many topics should the forum keep track of? If your visiting a large forum with topic IDs like 231874 and you read 200 topics, that cookie will become quite large (about 2000 bytes).
The second possible solution is using the database like Frank H suggested. However, it would mean at least two to three more queries (SELECT read topics, UPDATE new topics and DELETE old topics) for every single page view. Sure, one could use a HEAP table that will speed it up, but there's still the general communication overhead when talking to the database. Also, HEAP tables are only supported by MySQL and most hosts have set MAX_ROWS to a low value so that their customers don't use up too much memory.
The jury's still out on this one.