ZimmermannM I've removed our last Exchange server in a small single Exchange 2016 CU23 server environment. The answer to all your queries is in the article https://docs.microsoft.com/Exchange/manage-hybrid-exchange-recipients-with-management-tools just step through it and run some get commands to have a look at what the steps do before you start with the actual remove / set commands. I will say it seemed to be relatively straightforward for us.
Short answer to your questions from our experience - Install the 2019 Management tools before shutting down the Exchange 2016 server - it's the first steps in the article. Installing the management tools prepares the Schema / AD for Exchange 2019 so you won't be able to install a new Exchange 2016 server going forward but it's needed for the tools to work. Once installed you can temporarily shutdown the Exchange 2016 server to make sure all your recipient commands work as expected.
Regarding system mailboxes - Once you've installed the 2019 Management Tools and run through the rest of the article, the last step is Active Directory Cleanup - have a read through the CleanupActiveDirectoryEMT.ps1 script and get an idea of what it does. One of the steps removes the AD accounts of the system mailboxes as well as other tasks so that's taken care of. Regarding databases - nothing is mentioned in the article so I didn't do anything with our remaining database, the server was shutdown and being a VM has been archived never to be turned on again and at some point to be deleted.
Thanks to Microsoft for providing this option to remove the last Exchange server! Only question I have now is what do I need to do to remain supported going forward? Do I need to maintain the Management tools workstation with the latest Cumulative Updates? And is there any risk doing that, that those Updates will attempt to prepare AD again? Or do I just stick to the Exchange 2019 CU12 Management Tools going forward if I need to reinstall them or install on a new workstation?
Thanks.