Just talked with an O365 support rep on this issue. They said I will need to open a ticket with the On-Prem support team, and that it was paid support. They said it was a known issue, and gave me a link to this post (which I had already found and sent the link with my initial O365 ticket request. They also said it was basically the On-Prem teams problem and not O365.
I suspect that O365 changed the Graph segment of Azure AD and failed to coordinate with the Server Essentials 2016 team. Since Essentials 2016 was in that awkward place between SBS 2011 and Essentials 2019 of forcing transition into the cloud and removal of On-Prem services, it is likely this small segment did not seem important. Unfortunately many businesses likely used 2016 because 2019 did not have the Access Anywhere function many have leaned on since SBS 2003/2008.
O365 will likely not make any change that will allow the sync to work, and it will be on the Server 2016 to fix where the password sync tool attempts to connect with a patch or update.