Unable to telnet out on port 25 on windows server 2008

I just setup a Windows 2008 R2 server and am trying to get a basic mail server up and running so that I can send emails from my applications.

I setup a virtual SMTP server in IIS6 and tried doing a local telnet to port 25, which seemed to work fine. There were no errors during this stage and I can see the mail message appear in the Queue folder.

The problem is that mail never leaves the Queue folder. I then tried to telnet to a remote mail server on port 25 but couldn't connect:-

telnet 209.85.227.27 25

Could not open connection to the host, on port 25: Connection failed)

I checked my firewall and there is a default setting to allow all outgoing TCP traffic with no restriction. I even setup a specific rule for outgoing port 25 traffic but to no avail.

I then ran a SmtpDiag.exe command

 .\SmtpDiag.exe myemailaddress@serverdomain.com myemailaddress@gmail.com

and received the following output

Searching for Exchange external DNS settings.
Computer name is WIN-SERVERNAME.
Failed to connect to the domain controller. Error: 8007054b

Checking SOA for gmail.com.
Checking external DNS servers.
Checking internal DNS servers.
SOA serial number match: Passed.

Checking local domain records.
Checking MX records using TCP: gmail.com.
Checking MX records using UDP: gmail.com.
Both TCP and UDP queries succeeded. Local DNS test passed.

Checking remote domain records.
Checking MX records using TCP: gmail.com.
Checking MX records using UDP: gmail.com.
Both TCP and UDP queries succeeded. Remote DNS test passed.

Checking MX servers listed for myemailaddress@gmail.com.
Connecting to gmail-smtp-in.l.google.com [209.85.227.27] on port 25.
Connecting to the server failed. Error: 10060
Failed to submit mail to gmail-smtp-in.l.google.com.

Is there any other diagnostics I can do to figure out if it's my firewall or something else? I have removed antivirus to make sure that it wasn't causing the problem. Any ideas would be much appreciated.