Random DKIM Error "no key for signature" when sending to Microsoft email address

[samirv]

Steps to reproduce issue :

Prerequisite : Email channel in c4c is fully setup with regard to DKIM.

1. From c4c, send 10 emails to a microsoft email address

2. Check the signatures for dkim pass or failure

3. Note that some of the DKIMs fail with error "no key for
signature" (in my recent test : 2 of 10 emails had dkim failures with 8 DKIM passes)

--------------------------------------------------------------------------------------

Scenario :

Email channel is setup in C4C and DKIM is applied on our side and on SAP side.

Issue :

When I send an email from this channel in c4c to a microsoft email address, sometimes the DKIM shows as failed with "no key for signature".  For example I sent 10 emails and 2 of them fail on DKIM with this error.  This is concerning as providers are becoming stricter with DKIM it might lead to messages not reaching customers (note that the messages were received though)

I have contacted SAP on this and they are saying there is no issue on their side and that its an issue with Microsoft with a low dns lookup value and that I should contact Microsoft.  Has anyone else checked/tested this issue and found any solution to it or any advice other than to contact Microsoft?

--------------------------------------------------------------------------------------