Originally found this post on the Technet forums which links to this MS Exchange Team blog from a few years ago.

This cmdlet is great for discovering or removing messages by searching one or many mailboxes. Excellent for removing large messages sent to large distribution groups or virus/spam messages if identified early by the administrator, etc.

A couple of errors that might be returned by this cmdlet are:

[0] [ERROR] Error was found for (SourceMailboxEmailAddress) because: Error occurred in the step: Moving messages. Failed to copy messages to the destination mailbox store with error:
MAPI or an unspecified service provider.
ID no: 00000000-0000-00000000, error code: -1056749164

[0] [ERROR] Error was found for (SourceMailboxEmailAddress) because: Error occurred in the step: Creating target folder in the target mailbox. An unknown error has occurred., error code: -2147221233


These are permissions issues. The account running the command needs to have full permissions to the source mailbox (first error code) and the destination mailbox (second error code). This is explained well here

That said, also take a look at this if you are sure that permissions are set correctly

Post reboot of an Exchange public folder & mailbox server, this error was received by Outlook 2003 clients. Outlook 2007 clients had no problems. Reason is because the public folder database was offline, i.e. failed to mount. The following services had failed to start: Information Store, System Attendant and Service Host.

After restarting these services successfully, the Information Store was able to mount the PF database and the error is cleared for the clients. The PF database stored the offline address book for these clients and that was the object that could not be found.

This MS KB article, covers a different reason that the same error might be seen client side – because the selected OAB for the mailbox database the client was located on had an invalid (old, deleted, ???) offline address book configured.

Also, the reason that the services originally failed to start appears to be because the IS service was unable to contact an Active Directory domain controller when starting up:

Event Type: Error
Event Source: MSExchangeIS
Event Category: General
Event ID: 1121
Date: 10/8/2009
Time: 12:00:46 PM
User: N/A
Computer: PAC-MSG-HTR1
Description:
Error 0×96f connecting to the Microsoft Active Directory.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.

Possibly an idea to set the recovery action of these services to restart in X minutes time, especially if the site is recovering from a power outage or some other reason that both the Exchange servers and AD servers would be down or restart at the same time.

Finally, this link [msexchangeteam.com] has lots of good information on the various possible scenarios resulting in an 0×800401oF MAPI error