Ongoing issue with Outlook randomly disconnecting users.

Question

We have an ongoing issue with Outlook disconnecting our users. Outlook will disconnect and the users will get a pop up with the error message: There is a problem with your account. Please Try again later. Cancel is the only option they can then click. If they Click Cancel Outlook says it needs password. Clicking on Type Exchange password and connect bring them back to the same error message. When checking the connection status it just shows Error* under Authn. If we sign them out of office and try and sign back in we get another error message: Sorry, we are having some temporary server issues. The only options are Try again or Cancel. The only way we have found to temporarily cure the issue is to take the computer off the domain, rename it then put it back on the domain. Outlook then connects again no problem. It is probably worth noting we are using Azure AD connect to connect/sync our local domain AD with our Office 365 account. Oh and the Issue doesn’t occur on our Volume Licenced Office 2016 on our Terminal Server.