We normally see the 421 4.3.2 Service not available when attempting mail delivery to MS Exchange servers. There are a lot of different Exchange versions and setup procedures vary so we can't tell you 100% what the problem is.
From our research the problem is most often caused by not allowing our IP addresses to deliver mail to your server.
Check what IP addresses you are allowing to receive mail through the receive connector.
* TIP * Do you see the 421 status in your SMTP protocol log? That's usually where the receive connector sends errors when the IP address isn't allowed to use the receive connector.
You can read detailed setup instructions for Exchange 2007/2010 on how to receive mail from the Internet on this blog page (external site).
Here is another article (external site) that covers the creation of a receive connector with IP access controls.