The Microsoft Exchange Mailbox Replication service was unable to process jobs in a mailbox database - EventID 1006

After deleting a mailbox database from Exchange 2013 in one of my test environment, I was getting the following warning in the Application log of the server hosting that database:

Log Name:      Application
Source:        MSExchange Mailbox Replication
Date:          3/13/2018 7:16:44 AM
Event ID:      1006
Task Category: Service
Level:         Warning
Keywords:      Classic
User:          N/A
Computer:      server.domain.com
Description:   The Microsoft Exchange Mailbox Replication service was unable to process jobs in a mailbox database.
Database: Missing database (a435e9be-b010-400d-9d56-659065d6c9df)
Error: Database 'a435e9be-b010-400d-9d56-659065d6c9df' doesn't exist.

After running the cmdlet below, I confirmed that the database mentioned in the warning didn’t exist (so it was safe to assume it was the one I deleted):

Get-MailboxDatabase | FT Name, GUID -Auto

Most of the times, you can resolve this by simply restarting the Microsoft Exchange Mailbox Replication service or the Information Store service. Alternatively, rebooting the server will stop the warning since all the required services will be restarted.