I'm very disappointed to hear that you're removing UM from Exchange 2019 and I hope that you'll reconsider that decision. Or at the very least, allow for some sort of compatibility mode where mailboxes on Exchange 2019 can continue to be UM enabled as long as an Exchange 2016 server remains in the mix to handle the SIP trunks, etc.
The suggestion to use Cloud Voicemail as a replacement is not reasonable. First, if I'm still using on-prem Exchange its because I have various political and/or technical reasons why a cloud service doesn't work for my organization. So telling me to use a cloud service to replace functionality stripped out of my on-prem server just doesn't make any sense - if I could use the cloud, I'd be using the cloud. Second, even if I could clear the political and technical hurdles to using Cloud Voicemail, it's not even just a "drop-in" service. I also have to go deploy Skype for Business and (if I'm understanding the documentation right) toss out my IP-PBX. I hope I'm wrong about that, because there is no way I could get support for such a migration.
So, what should have been a straightforward upgrade/migration to Exchange 2019 during our next hardware refresh now becomes much more complicated and expensive since I'll have to purchase an on-prem voicemail system.