Exchange Server - Can't Send Email to a domain - QUEUE message expired

Sory for the late reply.
No that is not the correct output.

After telnet <dimain> 25

it will actualy open a telnet session on their exchange server.
telnet to a nother domain prefrably one of your componys partners and see the results.

1. For example, type:
2. telnet mail.contoso.com 25
3. Note You can replace servername with the IP address or the FQDN of the SMTP server that you want to connect to. Remember to press ENTER after each command.
   
   If the command works, you receive a response from the SMTP server that is similar to the following:

4. 220 site.contoso.com Microsoft Exchange Internet Mail Connector <version number of the IMC>

5. Note There are different versions of Microsoft SMTP or third party SMTP servers, and you may receive different responses from the receiving server. What is important is that you receive the 220 response with the FQDN of the server and the version of SMTP. Additionally, all versions of Microsoft SMTP include the term "Microsoft" in the 220 response.
6. Start communication by typing the following command:
   EHLO test.com
   Note You can use the HELO command, but EHLO is a verb that exists in the Extended SMTP verb set that is supported in all current Microsoft implementations of SMTP. It is a good idea to use EHLO, unless you believe that there is a problem with the Extended SMTP Verbs.
   
   If the command is successful, you receive the following response:

   250 OK

if you do recive the 250 OK command output you will be able to send Email messages to that domain .
http://support.microsoft.com/kb/153119

Thanks everyone for the help!

I tried the commands you suggested 

1. Telnet smtp.comcast.net 25
2. ehlo comcast.net
3. mail from:username@mydomain.com

I was not able to go beyond the 3 step.
I was getting different errors each time I tried the third command:

500 5.5.1 command unrecognized
550 5.1.0 Authentication required

I also looked on mxtools.com and got the errors/warnings below

 Reverse DNS FAILED! This is a problem.
 Warning - Reverse DNS does not match SMTP Banner

Check the Protocol Log (SMTP) and saw this error:

Comcast requires that all mail servers must have a PTR record with a valid Reverse DNS entry. Currently your mail server does not fill that requirement. For more information, refer to: http://help.comcast.net/content/faq/PTR",

Created the Reverse DNS record in my DNS server but still no luck.

If I do a nslookup for my ip i get:

non-existent domain

Checked the mxtools.com and get the same errors. Any suggestions? Is the PTR something I have to do on my dns server or is it something I need to ask my T1 provider to do?

Thanks in advance!

OK.

you need to create a smart host connector that sends all your external mail to your mail hygiene server that server has the appropriate MX records and DNS records for your domain.

what is happening now is you are sending from your exchange server then that server does a lookup and finds your MX record which is located at you ISP. thus they receive a different IP thus mail fail as it is mimicking spoofing