I am suddenly getting this message today for this recipient. I am replying to his email so I'm not retyping his email address.
The destination server for this recipient could not be found in Domain Name Service (DNS). Please verify the email address and retry. If that fails, contact your administrator.
It has been working up until today. I've done the blacklist check with our email but it doesn't show that we are blacklisted anywhere.