Microsoft Exchange 2013 - Cumulative Update 14

Had to work on a failing CU14 update on a Windows 2012 R2 box, running Exchange 2013.
The update was failing on step 5 - mailbox role.

The error log contained:

Error:The following error was generated when "$error.Clear();           if (($RoleIsDatacenter -ne $true) -and ($RoleIsDatacenterDedicated -ne $true))          {            if (test-ExchangeServersWriteAccess -DomainController $RoleDomainController -ErrorAction SilentlyContinue)            {              # upgrade the discovery mailboxes to R5 version, this will fix the RecipientDisplayType property of the discovery mailbox which was wrong in R4.              get-mailbox -RecipientTypeDetails DiscoveryMailbox -DomainController $RoleDomainController | where {$_.IsValid -eq $false} | set-mailbox -DomainController $RoleDomainController              $name = [Microsoft.Exchange.Management.RecipientTasks.EnableMailbox]::DiscoveryMailboxUniqueName;              $dispname = [Microsoft.Exchange.Management.RecipientTasks.EnableMailbox]::DiscoveryMailboxDisplayName;              $mbxs = @( get-mailbox -Filter {name -eq $name} -IgnoreDefaultScope -resultSize 1 );              if ( $mbxs.length -eq 0)               {                $dbs = @(get-MailboxDatabase -Server:$RoleFqdnOrName -DomainController $RoleDomainController);                if($dbs.Length -ne 0)                 {                  $mbxUser = @(get-user -Filter {name -eq $name} -IgnoreDefaultScope -ResultSize 1);                  if ($mbxUser.Length -ne 0)                   {                    enable-mailbox -Discovery -identity $mbxUser[0] -DisplayName $dispname -database $dbs[0].Identity;                  }                }              }            }            else            {              write-exchangesetuplog -info "Skipping creating Discovery Search Mailbox because of insufficient permission."            }            }        " was run: "Microsoft.Exchange.Data.DataValidationException: Database is mandatory on UserMailbox.".

What you are looking for is highlighted in bold.
A simple Exchange Powershell command would reveal the real culprit: Get-Mailbox
I got a list of all user mailbox, however, at the very top, there was an error saying that the Discovery Mailbox is corrupt.

To fix this I followed this Microsoft KB:
1. Run the following command to delete the default discovery mailbox

Remove-Mailbox "DiscoverySearchMailbox{D919BA05-46A6-415f-80AD-7E09334BB852}"

2.  In the message asking you to confirm that you want to delete the mailbox and the corresponding Active Directory user object, type Y, and then press Enter.
2.1 In my case, I had to restart the Exchange server, because it would not let me re-create the discovery mailbox, so keep that in mind.

A new user object is created in Active Directory when you create the discovery mailbox in the next step.
3. Run the following command to re-create the default discovery mailbox.

New-Mailbox -Name "DiscoverySearchMailbox{D919BA05-46A6-415f-80AD-7E09334BB852}" -Alias "DiscoverySearchMailbox{D919BA05-46A6-415f-80AD-7E09334BB852}" -DisplayName "Discovery Search Mailbox" -Discovery

4. Run the following command to assign the Discovery Management role group permissions to open the default discovery mailbox and view search results.

Add-MailboxPermission "DiscoverySearchMailbox{D919BA05-46A6-415f-80AD-7E09334BB852}" -User "Discovery Management" -AccessRights FullAccess -InheritanceType all

Once this is done, you can restart you CU and it should work.