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 "mydomain.tld" -Enabled $true
Note: Unless you’ve already added the necessary _domainkey CNAME records to your DNS zonefile, this command will succeed in generating the DKIM keys, but will fail to enable DKIM signing for the domain. Without looking into it I suspect that the Set-DkimSigningConfig cmdlet could be used to enable signing.
Finally disconnect from your O365 PS session:
Your domain now signs mail sent through O365 or via Exchange Online Protection.
Bonus knowledge: With a recent version of PowerShell Core installed, you can manage situations like this from a regular Mac or Linux box.