How about you use SPF records to verify the validity of a mail server like the rest of the industry?
We moved our client to a new internet connection and changed their MCX and SPF records accordingly (both records had a TTL of 60 seconds). 3 hours later, they told us O365 was blocking them. Check of industry blacklists and SPF Validity tests indicated noone else had a problem receiving their mail, it was just O365 being special
MX, not MCX