I think this could be a problem with the firewall.
Sometimes Exchange has difficulty interpreting the error message sent by the firewall when it can not connect to the mail server indicated by the primary MX record. What happens is that Exchange just keeps trying to send mail to the IP indicated by the primary MX and never switches to the secondary MX record.
I had this with a Watchguard firewall, and it was consitent for the domain, but not consitent in that not every domain that had a primary MX that could not be contacted caused a problem. I have never heard a good explanation ofr why this would be.
Anyway, there are a couple of ways to work around this. You can take off SMTP relaying at the firewall and set up a policy to let the Exchange server send out it's own mail through the firewall. (This can cause a future problem as your sending IP will now be different than your receiving, which can cause companies to this you're sending spam).
You can also hard code the primary and secondary DNS entires in your DNS, either at the firewall or internally. This sucks, as it's a nightmare to keep up with.
I was lucky in that it was limited to a small number of domains. Also, when I upgraded to 2003 it fixed itself, but the 2000 Exchange server could not be fixed.
Supposedly this problem was fixed in Exchange 5.5, but it keeps popping up on different threads across all versions of Exchange.
Here's another example: