*** Update 10 July 2020. This is a back end service issue that Microsoft is working on to resolve. See the following for more details – https://techcommunity.microsoft.com/t5/exchange/error-when-connecting-to-exchange-online-vis-powershell/m-p/1512141#M5466
To connect to Exchange Online with PowerShell you simply type a command like:
connect-exchangeonline
as shown above. This “should” work with Exchange Online PowerShell V2. However, as you can also see from the above screen shot this generates the following error on a number of tenants:
Import-PSSession : Data returned by the remote Get-FormatData command is not in the expected format
This therefore, prevents you from connecting to Exchange Online via PowerShell.
Interestingly, you get the same issue if you use the older method of connecting to Exchange Online via PowerShell (aka V1) to those same specific tenants. It is also independent of the device you use to connect, updates, etc. It seems to be tied to only a limited number of tenants for some reason.
The fix for now is to specify the –delegatedorganization parameter with the full .onmicrosoft.com user identity. When you do that, to exactly the same tenant, you can gain access as shown above without an error.
So, if you need access use:
connect-exchangeonline –delegatedorganization <tenantname>.onmicrosoft.com
and you should be able to gain access. The problem is that this is ok for interactive sessions but if you already have bulk automated scripted in place that don’t use this then it is painful to start changing these just to accommodate a ‘limited’ number of affected tenants.
I am chasing down some leads to try to determine a reason for this and hopefully find a resolution soon.
CIAOPS 
Great Post! Thank you! Your solution was the only one I have found that worked. Adding Serialization=Full to the connection URI still gave me the formatdata error.
I hope your leads pan out. This sort of thing happens all too often in MS cloud services.
I will spend the next few hours updating my automated scripts. Not ideal, but the only option. Thanks again for this post.
LikeLike
Did you ever find out what caused this? Got this today after attempting to connect my own tenant! The weird thing is that it imports the 700 commands and *then* fails with the obscure message
LikeLike
Yes I did. Basically it is an MS endpoint issue they need to fix and are addressing
LikeLike
See Fred Weinmann’s reply to this – https://techcommunity.microsoft.com/t5/exchange/error-when-connecting-to-exchange-online-vis-powershell/m-p/1507835
LikeLike
The problem began for us just this morning. Of all the various workarounds proposed, only these two V1 methods are successful on our tenant.
$O365Session = New-PSSession –ConfigurationName Microsoft.Exchange -ConnectionUri https://ps.outlook.com/powershell-liveid?DelegatedOrg=.onmicrosoft.com -Credential $o365Cred -Authentication Basic -AllowRedirection -WarningAction silentlyContinue
Import-PSSession $O365Session -DisableNameChecking -AllowClobber
– or –
$O365Session = New-PSSession –ConfigurationName Microsoft.Exchange -ConnectionUri https://ps.outlook.com/powershell -Credential $o365cred -Authentication Basic -AllowRedirection -WarningAction silentlyContinue
Import-PSSession $O365Session -DisableNameChecking -AllowClobber -Verbose -CommandName *
LikeLike