Okay, an update on this.
NOT THE ISSUE: Microsoft's issue listed here previously was not the issue unfortuanately.
I believe I had found the issue though! Fingers crossed, will be sure tomorow if not..
Back Story:
The Adaxes server lives on our network behind a proxy server. When first setting up Adaxes to use with Office 365 and trying to attach the Tenant, I had issues because the user could not get out. Why? Becauces the service user I was using did not have the proxy settings group policy setting (IE Proxy). So once I added that, I was able to connect to the tenant. From there on, adding users to Office 365 worked great as well. BUT not the Exchange settings, it only worked sometimes.
So once I remembered that connecting the Tenant was a Proxy issue, I started digging in that direction. One thing that was weird was that I would open up Powershell and try to connect to Exchange Online, and it was failing too. So It's just not a Adaxes thing, but something else. So, why do some non powershell to Office 365 work, and others (Exchange Online) don't?
Well, my theory here is that some use the IE Proxy settings, others (Exchange Online) use WINHTTP proxy settings.
My Adaxes server had WINHTTP settings of "Direct Access" in other words, Direct to the firewall, skip the proxy server. The firewall trusts any traffic through the proxy server, so it will let that traffic through. So by going directly to the firewall it would be blocked, unless that firewall has a specific rule to allow that traffic. Which it my case I think it would work sometimes based on what DNS returned for Outlool.Office365.com. I believe our Skype rule was letting it through, if we got lucky and it returned an IP that was in that rule.
WHAT Fixed this: Setting the WINTTP settings for the Adaxes server to point to the Proxy. Just incase others run into this and want to verify or set the WINHTTP proxy, it's done like this:
Show me the settings: netsh winhttp show proxy
Set the proxy: netsh winhttp set proxy {proxy address}