This turned out to be a known scenario, where Exchange 2019 does not install all necessary certificates when it noted an existing Exchange 2013 has a compatible certificate that it can piggy-back off of. When Exchange 2013 was retired from the domain, that certificate was no longer available, and caused "quirky" behavior with Outlook clients.
The following simple commands regenerated the certificate and put it in place:
New-ExchangeCertificate -KeySize 2048 -PrivateKeyExportable $true -SubjectName "cn=Microsoft Exchange Server Auth Certificate" -FriendlyName "Microsoft Exchange Server Auth Certificate" -DomainName "OURDOMAIN"
$Thumbprint = (Get-ChildItem -Path Cert:\LocalMachine\My | Where-Object {$_.Subject -match "Microsoft Exchange Server Auth Certificate"}).Thumbprint;
Set-AuthConfig -NewCertificateThumbprint $Thumbprint -NewCertificateEffectiveDate (Get-Date)
Set-AuthConfig -PublishCertificate
Set-AuthConfig -ClearPreviousCertificate