I have used various versions of O365 Office 2016 (MSI or Click-to-Run) versions without any issues.
Technically, if everything is setup correctly, you shouldn't even need to roam the cached credentials. (Credential Manager) Like does your user UPN match the SMTP address? (It Should)
First of all, I'd check to see if you O365 Tenant has Modern Authentication enabled. It used to be OFF by default, but sometimes in early 2017 Microsoft changed it to ON by default.
If it's off, you use Basic auth. When it ON, you try Modern Auth first, then fall back to Basic auth if you app needs it...like Office 2010 or Office 2013 without the EnableADAL registry key.
Modern Auth = Success
Also, ensure you have the UEM ADMX file for Office 2016 setup to "Automatically activate Office with Federated organization credentials".
Hopefully, this will lead you down the path towards success!
Thank you for the suggestions! I am testing this with a O365 account that is cloud only. I do not have ADFS SSO setup. The tenant was setup this year so I am sure modern authenication is enabled. I will try that disabling that GPO setting. Maybe O365 is excepting federation account but it's not setup. Thanks!