I spent half of my Saturday troubleshooting this problem only to learn a bug in the PS script put me on a wild-goose chase. While installing a new on-premises CRM 365 I came to the step to connect it to Exchange Online. When running the configurecrmserversidesync.ps1 script the process failed with the error "Office 365 credentials aren't valid." There's very little documentation on this script so to troubleshoot I had to guess at what logon format the script was expecting. When none of those varying formats worked, I tried many combinations of user permission configurations in Office 365 and continued to get this error. When I was about to throw my keyboard across the room in frustration I looked at the contents of the PS script file and I saw this line:
if(!(Test-Connection -ComputerName $rootDomainName -Quiet)) { ExitWithError("Office 365 credentials aren’t valid.")
This line determines if the CRM server responds to ping, and if not, throws the error "Office 365 credentials aren't valid.". I enabled the rule in the CRM server firewall that allows ping and the script ran successfully. Literally a 30 second fix that I wasted hours on thanks to Microsoft sloppiness. You wouldn't see this kind of sloppiness from Google.
*This post is locked for comments