Email rejected - Recipient address rejected: [DNS_NAME] Sending domain hosted on bad dns server

Email rejected - Recipient address rejected: [DNS_NAME] Sending domain hosted on bad dns server

Hi,

Getting a random bounce back from a vendor of ours when sending an email to them.

"Recipient address rejected: [DNS_NAME] Sending domain hosted on bad dns server"

Not quite sure what I can do to fix this.

Many thanks.