I've been banging my head and searching for answers for this for about a day and a half now. Is there something I'm doing wrong? Both mailboxes are shared mailboxes, one is soft deleted the other is active.
PS> (get-mailbox -SoftDeletedMailbox recoverytest@mydomain.com).ExchangeGUID
Guid
----
222d4b9c-6439-4eec-b467-143353667ace
PS> (get-mailbox recoverydestination@mydomain.com).ExchangeGUID
Guid
----
af5cbbcb-2366-4cf1-80df-a518b5e47b1b
PS> New-MailboxRestoreRequest -SourceMailbox 222d4b9c-6439-4eec-b467-143353667ace -TargetMailbox af5cbbcb-2366-4cf1-80df-a518b5e47b1b -Verbose
Mailbox "222d4b9c-6439-4eec-b467-143353667ace" doesn't exist on database "NAMPR15DG135-db049".
+ CategoryInfo : NotSpecified: (:) [New-MailboxRestoreRequest], MRSRemotePermanentException
+ FullyQualifiedErrorId : [Server=BN7PR15MB2340,RequestId=aaf723b2-0951-47a9-8f8a-19a618f800ec,TimeStamp=11/19/201
9 3:34:08 PM] [FailureCategory=Cmdlet-MRSRemotePermanentException] BE96E07B,Microsoft.Exchange.Management.Migratio
n.MailboxReplication.MailboxRestoreRequest.NewMailboxRestoreRequest
+ PSComputerName : outlook.office365.com