To follow up from Dan's response we used the "Outlook" setting in the email setup and still the same problem. They are remote accessing into a Windows Server 2012 R2.

We will try using the "Direct" method to see if that wins us any battles.