I've tried several things so far, including removing the user/user.seen file and restarting (that made all messages unseen, but even then after I used Thunderbird to mark all read again, the problem is back.
I've restore the mail spool and tried just "reconstruct" (didn't seem to help), and "cyrus reconstruct -G -R -V max" (which made a big mess).