[exim] Email DNS Issue

I am running bind 9.2.4 and exim-4.60-1. I have a user complaining
they cannot receive email from a certain person. I see in the log
files: "temporarily rejected ... Could not complete sender verify".
They have had this issue for weeks. The sender never receives a
bounce either.

I went to Dnsstuff.com and checked out sending domain. What looked
glaringly wrong to me is this:

"ERROR: ns.abcuser.net. has a CNAME entry
(ns.abcuser.net.->ns1.xyzuser.net.); it is not valid to have a CNAME
entry entry for the hostname in an NS record (for ns.abcuser.net.).
See RFC1912 2.4 and RFC2181 10.3 for more information.
ERROR: ns1.abcuser.net. has a CNAME entry
(ns1.abcuser.net.->ns1.asdfuser.net.); it is not valid to have a CNAME
entry entry for the hostname in an NS record (for ns1.abcuser.net.).
See RFC1912 2.4 and RFC2181 10.3 for more information.
Note: This test checks with our local DNS server (since the NS record
hostnames may not be handled by your DNS server), and therefore may be
cached."

And also:

"MX A lookups have no CNAMEs WARNING: One or more of your MX records
points to a CNAME. CNAMEs are prohibited in MX records, according to
RFC974, RFC1034 3.6.2, RFC1912 2.4, and RFC2181 10.3. The problem MX
record(s) are:"

I do a dig(dig domain mx) for the mx on my dns server and get a
SERVFAIL, dig on @AT&T dns server and it works. Dig on @Qwest DNS
server and it does SERVFAIL. But later it works on the Qwest server.
Does the sender verify in Exim just do a mx lookup or what?

They say they do not have trouble emailing anyone else. I really do
not have trouble receiving email from anyone else with over a thousand
heavily used accounts. So is this likely my problem or a problem at
the sending domain?

Matt