Exchange 2016 & Outlook Anywhere - Repeated Authentication Popup when Outside Network

Question

Exchange 2016 on-premises, Outlook 2013/2019

When a user is inside the network/on the VPN everything is fine.
When a user brings their laptop outside of our network: Outlook pop-ups asking them to log into their mailbox.
If they enter their domain credentials the pop-up will disappear & reappear immediately.
If they ignore the pop-up they can still send and receive mail!

The lower-right area of the status bar in Outlook says "Needs Password". If you click on that it switches to "Connected to: Microsoft Exchange" until the pop-up returns a few minutes later.
Outlook's Connection Status window shows the connection is established.
Opening Outlook in safe mode does not help.

I ran Get-OutlookAnywhere in EMS:

RunspaceId                         : #####  
ServerName                         : #####  
SSLOffloading                      : True  
ExternalHostname                   : #####.#####.###  
InternalHostname                   : #####.#####.###  
ExternalClientAuthenticationMethod : Basic  
InternalClientAuthenticationMethod : Ntlm  
IISAuthenticationMethods           : {Ntlm, Negotiate}  
XropUrl                            :  
ExternalClientsRequireSsl          : True  
InternalClientsRequireSsl          : False  
MetabasePath                       : IIS://#####.#####.###/W3SVC/1/ROOT/Rpc
Path                               : C:\Program Files\Microsoft\Exchange Server\V15\FrontEnd\HttpProxy\rpc  
ExtendedProtectionTokenChecking    : None  
ExtendedProtectionFlags            : {}  
ExtendedProtectionSPNList          : {}  
AdminDisplayVersion                : Version 15.1 (Build 845.34)  
Server                             : #####  
AdminDisplayName                   :  
ExchangeVersion                    : 0.20 (15.0.0.0)  
Name                               : Rpc (Default Web Site)  
DistinguishedName                  : CN=Rpc (Default Web Site),CN=HTTP,CN=Protocols,CN=#####,CN=#####,CN=Exchange Administrative Group,CN=Administrative Groups,CN=#####,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=#####,DC=###  
Identity                           : #####\Rpc (Default Web Site)  
Guid                               : #####  
ObjectCategory                     : #####.###/Configuration/Schema/ms-Exch-Rpc-Http-Virtual-Directory  
ObjectClass                        : {top, msExchVirtualDirectory, msExchRpcHttpVirtualDirectory}  

The reason this works inside the network is obviously due to Basic/NTLM authentication, but I don't see why Basic would cause the issue we experience outside.

I have found many forum posts suggesting solutions such as changing Outlook profile options in the security tab (Logon network security, Exchange Proxy Settings, http, etc).
Those profile options are either nonexistent or greyed out in Outlook 2013/2019. I think they might be dictated by Exchange but I am not sure how.

 
Weirdly, one 2019 user does not get the standard Outlook username/password popup. She gets a popup asking for her "work or school account". When she enters her work e-mail address there's an error saying "This organization doesn't support joining Azure AD."
We don't use Azure in our company. This popup follows her between computers. This behavior baffles me.

 
I'm not sure when this issue developed or why, but I'm reasonably certain the fault is with Outlook Anywhere.

Is this an Outlook Anywhere misconfiguration?
Is this an authentication issue?
Is this a SSL issue?

Any advice is appreciated.
Thank you!

Solution

Figured it out. It was a DNS or firewall issue (depending on where you're more comfortable instituting the fix).

Our server is configured to provide two mail domains for each user. One is current, one is legacy.
Our hosting company changed our public IP address and the firewall was updated accordingly.
The current DNS record was updated to the new IP. The legacy DNS was not. The legacy record still pointed all of the CNAME entries (autodiscover.legacy.com, mail., etc) to the old IP.

The old IP would have worked if the firewall was set to accept & route traffic accordingly. I opted to update the legacy DNS record instead.

Thanks for your advice, @Kelvin_D!