How are you generating the emails that fail? Is it manually or programmatically.
I have no issues anymore (!) sending emails to either gmail or microsoft from the webmail or using an ipad/iphone. All my emails go through without being flagged as spam or any other errors. However in order to get to this point you need to get on a whitelist with MS as explained below. This does not solve the issue of the mismatch.
For google i needed to a txt record for google-site-verification