I'm going to assume that you are not using Windows Small Business Server (SBS) and, therefore, ISA Server is not playing a part in this. There is a fantastic tool called SmtpDiag.exe available for download from Microsoft. It will help you identify why inbound email is not being accepted. If your external MX records were altered, it could cause telnet and other hosts to point at the wrong server.
Since you mentioned that you were just the victim of an open SMTP relay from a spammer, you'll also want to make sure that your outbound email is not adversely affected. You can check to see if your SMTP host IP address is on a blocklist at Spamhaus.
Do you have comments on this Ask the Expert Q&A? Let us know.
Ask an Exchange Server question in our forum.
Dig Deeper on Exchange Server setup and troubleshooting
Related Q&A from Richard Luckett
Some folders in a mailbox on Exchange Server 2013 are not showing up on the folder list in the OWA virtual directory but do appear in other views. Continue Reading
We have a Client Access Server and Mailbox Server on Exchange 2013 and we want to install an Edge Transport role on another machine. I joined the ... Continue Reading
How can I enable Outlook Anywhere to allow internal use for all users and external use for only some users in Exchange 2013? Continue Reading