Lets Exchange: Exchange Install Error Database is mandatory on UserMailbox

The other day I was trying to update the first Exchange 2013 server in this particular test environment to CU13 when I got the following error when installing the Mailbox role:

The error itself contained the code Exchange tried to run, so it wasn't clear what the exact problem was. An event in the Application event log mentioned the exact same thing:

Log Name:      Application
Source:        MSExchangeSetup
Date:          8/7/2016 2:34:52 PM
Event ID:      1002
Task Category: Microsoft Exchange Setup
Level:         Error
Keywords:      Classic
User:          N/A
Computer:      EX...
Description:   Exchange Server component Mailbox role: Mailbox service failed.
Error: Error:  The following error was generated when $error.Clear();
(...)

Time do dig deeper and look at the ExchangeSetup.log file! In here, I got some more information about what the problem was: Exchange was failing while trying to do something to the arbitration mailbox SystemMailbox{bb55...} (the one used in the Offline Address Book generation process):

[08/07/2016 10:34:51.0582] [2] Processing object "domain/Users/SystemMailbox{bb558c35-97f1-4cb9-8ff7-d53741dc928c}".
[08/07/2016 10:34:51.0582] [2] [ERROR] Database is mandatory on UserMailbox.
[08/07/2016 10:34:51.0598] [2] [ERROR] Database is mandatory on UserMailbox.
[08/07/2016 10:34:51.0598] [2] [ERROR] Database is mandatory on UserMailbox.
[08/07/2016 10:34:51.0598] [2] Ending processing set-mailbox
(...)
[08/07/2016 10:34:52.0004] [1] The following 2 error(s) occurred during task execution:
[08/07/2016 10:34:52.0004] [1] 0.  ErrorRecord: Database is mandatory on UserMailbox.
[08/07/2016 10:34:52.0004] [1] 0.  ErrorRecord: Microsoft.Exchange.Data.DataValidationException: Database is mandatory on UserMailbox.
(...)
[08/07/2016 10:34:52.0004] [1] [ERROR] Database is mandatory on UserMailbox.
[08/07/2016 10:34:52.0004] [1] 1.  ErrorRecord: Database is mandatory on UserMailbox.
[08/07/2016 10:34:52.0004] [1] 1.  ErrorRecord: Microsoft.Exchange.Data.DataValidationException: Database is mandatory on UserMailbox.
(...)
[08/07/2016 10:34:52.0004] [1] [ERROR] Database is mandatory on UserMailbox.
[08/07/2016 10:34:52.0004] [1] [ERROR-REFERENCE] Id=SystemAttendantDependent___1DEE95834DBA48F2BB211C2FB6765A5A Component=EXCHANGE14:\Current\Release\Client Access\Unified Messaging
[08/07/2016 10:34:52.0004] [1] Setup is stopping now because of one or more critical errors.
[08/07/2016 10:34:52.0004] [1] Finished executing component tasks.
[08/07/2016 10:34:52.0036] [1] Ending processing Install-MailboxRole
[08/07/2016 10:36:39.0444] [0] CurrentResult setupbase.maincore:396: 0
[08/07/2016 10:36:39.0444] [0] End of Setup
[08/07/2016 10:36:39.0444] [0] **********************************************

But what exactly does it mean by "database is mandatory"? Checking all the arbitration mailboxes using the Get-Mailbox cmdlet, I noticed that this mailbox was corrupted, it did not have a database, and I received the exact same error as during the installation:

Looking at its properties in Active Directory, the homeMDB attribute was indeed blank:

There are two ways to fix this: either remove this arbitration mailbox using ADSIEdit, re-run the Exchange setup to re-create it and then use the New-Mailbox cmdlet to complete its configuration; or rehome the mailbox by running the following cmdlet: