For the last couple of weeks I have been working with a number of outside domains who have been receiving a 550 error, no MX or MTA found for [my domain]. At first it appeared to be isolated to domains that used Google's Postini service, which after working with one of those domains things are now working with them, but now it is appearing to be more widespread than just Postini clients.

Before we started having these issues, we had not made any changes to our DNS entry, IP or firewall. We can send no problem to any of these domains, but even when they reply to one of our messages, they receive this error.

2 weeks ago, just before we started experiencing this issue, we sent out a bulk mailing from our main email server because the company that we typically use for bulk mailing has been getting flagged as spam. I've checked a number of blacklisting servers and our internal domain is not flagged anywhere, but with the results that I'm seeing I'm not 100% convinced.

Since we started having the issue, we did make a change to our MX record in the following ways with the backstory in a nutshell...
We have our primary [] which was originally provided by our ISP and the organization once offered free email addresses to customers using that domain.

After years of this the [] mail entry was removed for [] when email was brought inhouse, and [] remained as a secondary MX for the few email addresses that used that name.

As a result of this issue, the 2nd MX record was removed from [] with the assurance of our ISP that it wouldn't impact any email. When I do DNS lookups on [] under the MX record I see the DNS name []. If I do a DNS/MX lookup on [] all I see is an A record which points to our email server, but no MX record, which we did contact our ISP about this and they say that is standard and we shouldn't see it. Would this be correct, I'm still skeptical that this may be our issue.

In the past I've had similar issues with other sites that we send to and ended up having to add the domain to my hosts/resolv file, but up to this point everyone that I've dealt with has had a web based email system so have not been able to test this. Has anyone had a similar situation happen to them, and if so, what is the best way to resolve it? Thank you.