I was having this same problem with mails that used to work and now were coming up with this error message.

The reason I was getting it I found out was that client had changed their email addresses to a domian that didn't exist(!) - there was a typo in their domain name!
Once I had found it and changed it - it worked like a charm!

Thought it might help someone else who comes up against this problem