CNAME lookup failed temporarily. (#4.4.3)

Hi, Experts.

I’m looking for some help regarding this issue. I have a Windows | Linux DNS (issue is presenting regardless of wich DNS I use), and I have an e-mail server on Windows 2000 platform. Emails are being delivered fine, as well as received, but not for all domains. The main concern is for e-mails received from Yahoo. I can send e-mails to yahoo, but not receive from it. The following error shows up:

CNAME lookup failed temporarily. (#4.4.3)

I have verified, and there is an Alias (CNAME) for my domain. If I do a CNAME look up using several tools, I can find this record.

Any suggestion about the possible cause of this issue will be highly appreciated.

Best Regards.