Sometimes a newly added domain in Microsoft EOP will not let you enable DKIM from the web user interface. The only workaround I know of is to prepare the domain using PowerShell.
To connect a PS session to O365, I use the following script, ripped straight from Microsoft’s documentation:
$UserCredential = Get-Credential
$Session = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUri https://outlook.office365.com/powershell-liveid/ -Credential $UserCredential -Authentication Basic -AllowRedirection
Import-PSSession $Session -DisableNameChecking
After waiting for an eternity for the necessary stuff to load, run the following command – and wait another eternity for it to finish:
New-DkimSigningConfig -DomainName “yourdomain.com” -Enabled $true
selector1._domainkey.yourdomain.com. CNAME selector1-###._domainkey.###.onmicrosoft.com selector2._domainkey.yourdomain.com. CNAME selector1-###._domainkey.###.onmicrosoft.com