Question : Domain of Sender Address Does Not Resolve

I just changed DNS host from ZoneEdit to Network Solutions. Since the change we have been experiencing problems sending mail (mail delays) to certain, not all, domains.
I see in the queue - Error 451 4.1.8 Domain of Sender Address "email" Does not resolve.

I assume we have some problem with our DNS setup at NetSol.
Here is out setup. MX records point to Postini. I have A Records for out Exchange server and Firewall - mail.mydomain.com and fire.mydomain.com

SPF is "v=spf1 a:fire.mydomain.com;mail.mydomain.com mx a:mail.mydomain.com;spf.postini.com ~all "

Out ISP has PTR records for mail.mydomain.com and fire.mydomain.com. The reason I have the firewall A record in SPF and PTR is outgoing mail headers are sometimes tagged with the firewall IP -

What is missing/wrong? Any help would save my but.

Thanks,

Answer : Domain of Sender Address Does Not Resolve

Did you remove all entries at ZoneEdit? DNS Clients might still ask for data at the old address.

With all DNS answers there is a TIME TO LIVE (specified in seconds) and it's before the record type.
If not specified the default depends on configuration for Zone or DNS server.

Mostly TTL's of 1 day are used, so if you cutover a DNS, it will still take a day for all Caches to forget about previous answer.
same for server changes etc. the old address might be kept for a while in OTHER DNS server you cannot control.

Cutovers involving DNS (records) are preferably done by first +/- 24 hours ahaed of time change the TTL to say about 1 minute.

When cutover time arrives, you change all DNS records involved (still with short TTL)  and if all is sattisfactory you can remove the short TTL and get back to default. (If your addresses are stable there is no need to have every system in the world needing you address to have to ask it frequently, needless burdon on the DNS infra structure)
Or if conversion fails you can cutback....

If the above is the case it will probably fadeout after 24 hours since the cutover.