My issue in particular related to the decommissioning of a Exchange 2003 server. This server was turned off; then another Exchange server stopped sending/ receiving emails. However, all other Exchange instances were working correctly.
Cause was tracked down to the "Smart host" settings entry referring to the decommissioned server.
Exchange server> Protocols> SMTP> Default SMTP Virtual Server > Right click Properties
Delivery Tab > Advanced > "Smart Host" entry
In my case i could simply remove the entry as it was not required.