In your Exchange environment, mailbox moves are a normal routine for an administrator, however on the odd occasion you do have 1 or 2 that fail, below is a failure of a mailbox move:
“Error: Mailbox XXXXX tombstone is present in the target database. It must be cleaned up before the move operation can proceed.”
To fix this error, you would need to export the mail to a .PST file and re-create the mailbox and then import the .PST file again.
Rebooting the server or DAG does not make any difference.
Hope it helps.