Do you have more than one mailbox server? Do you have more than one public folder store? If yes to both they need to be replicating to each other. A useful tool for working with Public Folders is PFDAVAdmin. Download and install version 2.8 to your pc, not the exchange server.