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