Exchange 2013: A valid Migration mailbox could not be found for this organization.

Although the migration arbitration mailbox is created upon initial installation of your Exchange organization, due to corruption or general lack of the account (randomly goes missing!) you can easily re-create it as follows:

Firstly verify the account (Migration.8f3e7716-2011-43e4-96b1-aba62d229136) does not exist:

Get-Mailbox -Arbitration | fl name, alias

Re-run the following Exchange command (don't worry it shouldn't harm anything in your existing environment!):
setup /preparead/IAcceptExchangeServerLicenseTerms

Proceed by enabling the arbitration account used for migration (not enabled by default):
Enable-Mailbox -Arbitration -Identity "Migration.8f3e7716-2011-43e4-96b1-aba62d229136"

and configure it as follows:
Set-Mailbox "Migration.8f3e7716-2011-43e4-96b1-aba62d229136" -Arbitration –Management:$true

Finally we can verify the account with:
Get-Mailbox -Arbitration | fl name, alias

and

Get-MigrationUser