Hi, @BP-7667
It sounds like you have a well-thought-out plan to move Exchange 2016 to the cloud and set up a hybrid configuration with Exchange 2019.
Here are some considerations:
1.It's a good idea to use a staging server with Entra Connect to sync directories and run the Hybrid Configuration Wizard (HCW), you can opt for Modern Hybrid, which maintains a seamless mail flow without downtime, and can keep emails send/receive. Migrating mailboxes in phases is a wise decision that allows you to address any issues that arise and ensures a smoother transition.
2.Once all mailboxes have been migrated to the cloud, you can remove Exchange 2016 from your on-premises environment. However, be careful when removing Exchange objects from Active Directory (AD). Ensure that all necessary objects are properly cleaned up to avoid any conflicts when installing Exchange 2019.
3.After you remove Exchange 2016, you can continue to install Exchange 2019 on the new server. Rather than simply deleting the Exchange server, follow the proper procedure to deactivate Exchange to ensure that all Exchange-related objects are properly cleaned up from your on-premises Active Directory. Ensure that you follow the correct steps to extend your AD schema to support Exchange 2019 and configure the necessary connectors and certificates.
More information can be found How and when to decommission your on-premises Exchange servers in a hybrid deployment | Microsoft Learn
4.Removing Entra Connect and installing it on a new server should have no problem, it doesn't remove user accounts from Azure AD, just make sure to thoroughly clean up the old installation before setting up a new server to avoid duplicate accounts.
5.Microsoft allows you to run Exchange 2019 servers for hybrid purposes only, without additional licensing, and you can use Exchange 2019 for hybrid setups.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".