Exchange 2013 has a bug that causes this error message to be returned when sending email / telnetting to port 25:
421 4.3.2 Service not available
Restarting the Microsoft Exchange Hub Transport service resolves the issue temporarily, but it returns within a few hours.
Apparently this issue is caused by adding a custom Receive Connector in Exchange 2013 and choosing the Hub Transport Role instead of the FrontEnd Transport Role for the receive connector.
The solution, (aside from restarting the Transport service every hour) is to remove any Receive Connectors that you have added to the server (you can leave the default ones in-place), and recreate your receive connectors using the FrontEnd Transport option.
Word on the street is that Microsoft don’t consider this a bug ?!?
Oh well, I have made the changes to my Exchange 2013 server, and testing now to confirm all is well.