These instructions are useful to remove the Exchange server from an AD environment completely. Note that users email accounts must have been moved elsewhere.

Disable (DO NOT DELETE) mailboxes using ECM Console

Get-Mailbox -Arbitration | disable-mailbox -Arbitration -DisableArbitrationMailboxWithOABsAllow –DisableLastArbitrationMailboxAllowed
Get-Mailbox -AuditLog | Disable-Mailbox 
Get-Mailbox -Monitoring | Disable-Mailbox
(Thanks JitenSH https://community.spiceworks.com/topic/2003351-uninstall-exchange-2016)

$dbs = Get-MailboxDatabase (this will create a variable with the database name)
Get-Mailbox -Database $dbs (will list all remaining mailboxes. In my case it was the discovery search mailbox)

Delete the Discovery Search mailbox:
Get-Recipient *search* (this will display the full name of the discovery mailbox)
Remove-Mailbox "NAME FROM ABOVE"

Use Control Panel to uninstall exchange.

Sources used:
https://community.spiceworks.com/topic/2003351-uninstall-exchange-2016
https://docs.microsoft.com/en-us/exchange/security-and-compliance/in-place-ediscovery/delete-and-re-create-default-discovery-mailbox

...