Dory, BMJ, I'm having exactly the same problem.
This morning I received an e-mail that Setab had sent me a PM. When I logged into the board I saw the usual upper-right greeting "Hey, Nords, you have 55x messages, 1 is new." However Setab's PM, the new one, didn't display. I didn't pay attention to the last digit of the message (I will from now on!) but I think it was 554.
I went back to my PM index and deleted two old PMs. Still no Setab PM. I poked around the board for a while and when I returned to the PMs the server (or my cache) had updated to announce "Hey, Nords, you have 552 messages, 0 are new." I scrolled down to the bottom of the screen and Setab's PM was there.
What's the PM limit? Please let me know if 500+ PMs is a bad idea. I'd like to think that our recent problems are caused by that Asian porn spammer but I might be hogging a lot of the server's PM space...