Hi John and welcome to the forums!
Without looking at a sample of email, all of it would be assumptions. Some ideas:
- Recent change or did not propagate to all nameservers
- Email was forwarded and modified prior to be received by 365
- Issue with the receiver in performing the verification
- Private and public key missmatch
There could be others. A fail, instead of reported as a temperror or permerror is most often due to a signature verification failure (sig did not match) or public key record missing. It isn’t, but issues with DNS on either side could have resulted in that verdict.
Since the reporter is Enterprise Outlook, you can search for the sending IP in the raw XML report and review the envelope-to domain, which will tell you who this email was sent to. You may be able to speak with the receiver to obtain a copy of the headers. While the policy applies says reject, MS365 does not reject email, instead they quarantine them. This is assuming the receiver did not apply a custom block on them of course.
I hope this helps and good luck with your investigation.
