A lo mejo0r podrías añadir un campo en la tabla de usuarios con la fecha en timestamp de la petición de marcar todos como leidos y borrar en la tabla de leidos todos los de fecha anterior.
Pero entonces a la hora de tener en cuenta los leidos tendrías que tener en cuenta que los de fecha anterior a ese nuevo campo que añadiste se suponen leidos además de los que están en la tabla de leidos (jo vaya lio me monte yo sólo
).
No se si servirá. A ver que nos dice Cluster.
Salu2 ;)