Since about a month ago I can no longer send to any gmail accounts, but they can send to me. It doesn't even attempt to send and holds it in the queue with "451 4.4.0 DNS query failed. The error was: DNS query failed with error ErrorRetry". Eventually a bounce back occurs with the following: '400 4.4.7 Message delayed' saying the message will reattempt delivery in a couple of days.
Sometimes the message will actually be sent to the gmail account but it will be hours before it goes through.
I can query the mx record for gmail.com fine from my exchange server, so I'm not sure what the actual issue is here. I've also checked blacklists and we're fine.
Can someone give me an idea on where to look next?