Wanted to update this ticket with the solution we discovered. We were using privileged accounts in this situation to access the VM. These privileged accounts have the "$" character in them, e.g. myusername$@mydomain.com. Turns out that the "$" character is not supported in UPN. Per Microsoft's rep:
the dollar sign is not in the list of allowed UPN symbols, at least according to the standard we adhered to when wrote the name validation. This explains why the login is not working.
and
Unfortunately, the name becomes a part of the URL for permission and Microsoft Graph calls and $ sign has a special meaning in the URL format and may need to be escaped in several places across the several service calls, so it probably will not be as simple as adding it to the list of allowed UPN characters.
When I tried the AAD login using a "regular" account without any special characters, it worked as expected. Going to mark this as accepted and live to fight another day.