Exchange - Problem with receiving emails

I have a problem where some companies are unable to send me emails. When they try, they receive the following message: 554 5.4.0 < #5.4.312 smtp;550 5.4.312 Message expired, DNS query failed>

I have checked my DNS and health status in Microsoft, and everything seems to be correct.