Well, here at Posetteforever we've 2 ways of storing these informations: the default was by cookies , the other one is called UPI2DB ("Unread posts info to database" or something like that), your information is stored in the site's database, it's activated when you see in the top row New (-) U (-) M (-) P (-), that is New messages from the last visit, Unread messages , M ... I don't remember
and private messages
If you see it, the problem is probably on this side, if you don't see it you're set up with cookies (the option can be changed in your control panel).
UPI2DB worked fine for me till now, better then cookies but we are having some problems with the database so it can be something wrong...