Milter-greylist

Hi list,

I've recently installed milter-greylist on 2 new servers. But I'm
running into a strange problem. Everything seems to work fine, except
for mails coming from Microsoft domains.
Every time someone sends an e-mail from a Microsoft domain,
milter-greylist throws a fit:

Nov 20 15:45:37 localhost milter-greylist: DKIM failed: Key retrieval failed
Nov 20 15:45:37 localhost sm-mta[26871]: wAKEjaDU026871: Milter: data,
reject=451 4.3.2 Please try again later

This happens ONLY on Microsoft domains. And on every mail and re-send.
All other domains are handled normally it seems. I've been searching for
reasons, but coming up empty. The only weird thing I can find is that
Microsoft seems to have some configuration issues on DKIM:

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=outlook.com; 
s=selector1;

nslookup:
/root@myhost:~# nslookup//
//> set q=txt//
//> selector1._domainkey.outlook.com//
//;; Truncated, retrying in TCP mode.//
//Server:         127.0.0.53//
//Address:        127.0.0.53#53//
//
//Non-authoritative answer://
//selector1._domainkey.outlook.com        canonical name =
selector1._domainkey.outbound.protection.outlook.com.//
//
//Authoritative answers can be found from://
//> selector1._domainkey.outbound.protection.outlook.com//
//;; Truncated, retrying in TCP mode.//
//Server:         127.0.0.53//
//Address:        127.0.0.53#53//
//
//Non-authoritative answer://
//*** Can't find selector1._domainkey.outbound.protection.outlook.com:
No answer//
//
//Authoritative answers can be found from:/

That's not good? Can't resolve the DKIM signature? So it would make
sense that milter-greylist doesn't like it. But this can't be the
reason? Or the whole world would have this problem?

Anyone have any suggestions? If it's possible to turn off DKIM checking
that would be fine too AFAIC (preferably without the need for
recompiling). I've even whitelisted every outlook SMTP server (took me
an hour, they have some nice configuration issues there too :-(), but
that doesn't seem to help

Any help would be appreciated,

Thanks in advance,
Stefan