"451 Could not verify recipients" Message - Intermittent

[rwright]

We have been having problems receiving emails from certain domains. First it was just 1, and they said their IT team "did something" and then all was fixed. The next day two more customer domains could not send. Magically, all was fixed. I had not done anything to my Exchange 2003 (Server 2003) system at that time. I rebooted the server and then some was received but I don't know if it was a coincidence or not. I have since moved the server to a new area (planned) so it was rebooted at that time.
Now I have others telling me they are having problems from another domain and I tried my yahoo and hotmail but only the hotmail message came in.
I got a return in my yahoo that said:
----- START -----
<recipient email address was here>:
208.65.145.12 failed after I sent the message.
Remote host said: 451 Could not verify recipients (b2c6c464.2505739184.3583.00-013.p02c12m016.mxlogic.net): All MX server are unavilable for domain <our domain was inserted here> (Mode: normal)
I'm not going to try again; this message has been in the queue too long.
----- FINISH -----
Google searches suggested I restart SMTP but that did not fix anything. No errors in the logs and queues.
Any ideas?

 

[rwright]

Problem solved. Spam filtering company changed some IP addresses and these were not in the firewall.