Muitos dos softwares de fóruns maiores usam uma tabela de rastreamento para acompanhar quem leu o que, algo assim (bastante simplificado):
CREATE TABLE topic_tracking (
user_id INT NOT NULL,
topic_id INT NOT NULL,
last_visit DATETIME NOT NULL,
PRIMARY KEY (user_id, topic_id)
)
Você então usa uma junção nesta tabela para verificar se uma postagem que você está exibindo é lida ou não. Como você estará paginando seus tópicos, isso deve gerar relativamente poucas consultas adicionais (dependendo de quantas postagens você mostra por página).
Quando um usuário visita o encadeamento, atualize esta tabela de rastreamento com o carimbo de data/hora de sua visita. Então, ao exibir os links do seu tópico, verifique esta tabela para ver se o last_visit deles é anterior ao último post no tópico. Isso também permite que você mostre tópicos "atualizados", não apenas "novos".
