We had a number of cases of this logged on one of our servers. I checked the forums and tech notes, found http://www.symantec.com/business/support/index?page=content&id=TECH51036 and started to investigate.
The messages looked OK but the issue in our case was caused by the Exchange mailbox and quotas. The mailbox was enabled for Retention Hold and it had hit Database Quota Default (RecoverableItemsQuota)
Nothing could be archived (removed from the mailbox) as nothing could be added to the mailbox database.
Quick removal of the quota (Set-Mailbox alias -UseDatabaseQuotaDefaults $false) and archiving resumed. Obviously the quota issue needs addressing.