Tienes toda la razón no se pueden barajar cadenas tan larga ni en una cookie ni como registro de una bd.
He estado mirando como lo hacen los foros phpbb y es exactamente como dice cluster, con la salvedad de que registra los identificadores de topicos no leidos en vez los id de los posts. Pero el método es el mismo
Salu2 ;)