Let me throw in my own 2 cents to this topic because there are a lot of opinions on the cause of this failure. I setup my SMTP service on Windows 2008 R2. I have an account with an external SMTP relay service provider and I configured the account in the outbound connections page. I tested the mail via PS using the “send-Mailmessage” command. The mail goes to the queue folder and just sits there. I am testing this from my Hyper-V console at home on my Windows 8.1 client.
To troubleshoot, I go to my Azure server, its Windows 2012 but that should not matter, I put the same configuration on my SMTP service, do the exact same PS test and the mail is delivered successfully. So its either a DNS issue or something else, somehow the SMTP service is failing to make a connection to the SMTP relay.
I checked my DNS settings and that seems to work well. Then it may be that my ISP is blocking SMTP relay? As astounding as that may sound in this day and age, which is why this did not cross my mind to check, it may be true. They cannot be blocking their own relay agent, so I check their website and find out they do have an SMTP relay agent. I configure it in the outbound connections and my SMTP service begins to work well. I would still like to use a more commercial SMTP relay provider, their own relay agent is so slow, almost like a home grown agent. I have to find out why they are blocking SMTP relay.