JeremyTBradshaw This horse is mostly already dead, so this is the last I'll post on this until something changes, but I tested on yet another machine that very clearly works in an interactive PS session with the cert stored (CurrentUser\My). I also tested under LocalSytem with the cert in a .pfx file (works), in cert:\LocalMachine\My (fails due to cert not found), and in LocalSystem's cert:\CurrentUser\My. This last case fails with the same error as I was seeing on the other machine after I added it to LocalSystem's CurrentUser\My (via Import-PfxCertificate):
New-ExoPSSession : Invalid provider type specified.
.
At C:\Program Files\WindowsPowerShell\Modules\ExchangeOnlineManagement\2.0.3\ExchangeOnlineManagement.psm1:481 char:30
+ ... PSSession = New-ExoPSSession -ExchangeEnvironmentName $ExchangeEnviro ...
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ CategoryInfo : NotSpecified: (:) [New-ExoPSSession], Exception
+ FullyQualifiedErrorId : System.Exception,Microsoft.Exchange.Management.ExoPowershellSnapin.NewExoPSSession
Which is to say, it seemingly found the cert, but something else didn't like either the cert, or the environment in some way. There are a number of reported causes for this type of error, but none seem to apply here - this is a working, non-CNG cert (proven both in .pfx and stored form), and the folder permissions on the Crypto\RSA folder are defaulted (as verified against https://support.microsoft.com/en-us/kb/278381).
Have a good weekend!