Gran parte del software de foro más grande usa una tabla de seguimiento para saber quién ha leído qué, algo como esto (muy 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)
)
Luego usa una combinación en esta tabla para verificar si una publicación que está mostrando se lee o no. Dado que estará paginando sus hilos, esto debería generar relativamente pocas consultas adicionales (dependiendo de la cantidad de publicaciones que muestre por página).
Cuando un usuario visita el hilo, actualice esta tabla de seguimiento con la marca de tiempo de su visita. Luego, cuando muestre los enlaces de su hilo, verifique esta tabla para ver si su last_visit es anterior a la última publicación en el hilo. Esto también le permite mostrar hilos "actualizados", no solo "nuevos".