Intermittent Sender Domain Must Exist errors from remote SMTP hosts

[robertd040 at aol.com]

Hi everyone,

I'm having an intermittent problem with outbound email.  I will
intermittently get an error from a remote smtp host that indicates
that the reason for the rejection is "Sender Domain Must Exist", I've
also seen "DNS: FAILURE" or "Sender Domain must Resolve".  I've
checked and re-checked my zones, I've verified that my MX records are
correct (even though I don't see this as a problem because the MX
record is for OTHER people to find MY mail server with), I've
confirmed that my servers are delegated our reverse zone,
(in-addr.arpa) with our ISP, (Cable and Wireless)  , and from the
Internet all forward resolution works perfectly.  

I've been hearing a lot about anti-spam filters that SMTP hosts employ
to verify the validity of a SMTP message but I'm not sure this can be
ALL the problem.

I've got 6 zones that I'm currently "hosting" with two name servers.
All the zones are registered with Network Solutions and all the zones
have the same two DNS servers.  

ex. (truncated whois output)

XXXX.org

ns1.XXXX.org	123.123.123.123
ns2.XXXX.org	123.123.123.123

and

XXXY.org

ns1.XXXX.org	123.123.123.123
ns2.XXXX.org	123.123.123.123

etc..etc..etc..

I could include a huge amount of detail regarding my zones but it's
pretty basic and I've run tools like DNS Expert (miceandmen.com)
against the zones and they come up clean.

My two real questions are;

1).  Have I done a bad thing by "hosting" several different domains
with the same two name servers. (I don't think so)

2). What are these remote smtp hosts doing so strange that they won't
correctly resolve who's authoritative for my zones? and why is it
intermittent. (usually I can re-send and the mail will go through).

Thanks for anyones help.

Robert