Hi Jamison,
Even though the error message is slightly different the same issue persists. Although there is a registry edit available to resolve these problems I would not implement it for the simple reason that, although it is nice to avoid these problems popping up in the backup logs, there is no way to tell if a severe issue of corruption is ever occuring unless you manually review each backup log regularly.
Easiest thing to do is to logon to these two users mailboxes with an email administrator account, right click the root of their mailbox and select search. Then perform a search either by sender or by subject line as indicated in te corrupt messages above and simply delete them. You will have to also remove it from the deleted items folder.
It will not matter to the user as they would not have been able to view the message themselves anyways AND my experience has shown that asking and or relying on the users themselves to delete the messages rarely happens.
