I know there is a registry edit to have jobs not go into "failed" status for just corrupt Email items, but that doesn't seem to be the issue here. This issue looks a little different and the link supplied by the log (below) has nothing to do with the issue from what I can tell. Any thoughts?
V-79-57344-33928 - Access is denied.
Access denied to file Nick Vadan Top of Information StoreInboxHidden message. WARNING: "\\SERVER\Microsoft Exchange Mailboxes\Nick Vadan Top of Information StoreInboxHidden message" is a corrupt file. This file cannot verify. V-79-57344-33928 - Access is denied.
Access denied to file Rebekah Lysaker Top of Information StoreDeleted ItemsNotify from e-mail technical support.. WARNING: "\\SERVER\Microsoft Exchange Mailboxes\Rebekah Lysaker Top of Information StoreDeleted ItemsNotify from e-mail technical support." is a corrupt file. This file cannot verify.
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.
One more quick add-on question here. What would you consider the most effective way, step by step, to find and remove those corrupted items? Is there an easy way to do this from the Exchange Admin console?