SMPT Error: mail.XXXXX.com not found

This error arrived at my client’s site a couple of days ago. Exchange isn’t my forte, but we’d very much like to figure out what’s causing this. Initially, we thought the ISP was the culprit, but they claim connnectivity was confirmed in spite of the error message. Meantime, my client’s email is operating intermittently. Any suggestions on where the problem might be, anyone?