After deleting an unused mailbox database from Exchange 2013, you may see warnings appearing in the Application log (Event Log):

The Microsoft Exchange Mailbox Replication service was unable to process jobs in a mailbox database.
Database: Missing database (GUID)
Error: Database 'GUID' doesn't exist.

If removed very recently, wait for replication of AD throughout your domain, but the Mailbox Replication service will also cache the existence of the database. You can resolve this by simply restarting the Microsoft Exchange Mailbox Replication service (can be done during operation).