SMTP emails are failing from server

I am having an issue that I could use some help with.

I have a server that sends out SMTP emails through our Exchange 2007 server.  It works fine as long as I use only INTERNAL email addresses, such as:
Mike@mydomain.com
George@mydomain.com
etc.
(Mydomain.com = The name of my current work domain)
However, if I put in an outside domain, such as:
Mike@yahoo.com
The entire SMTP transmission fails.
On my Exchange 2007 server, I allowed this server to send emails through the "Internal Server Relay", which explains why we can send internal emails.  
Any ideas?

Another couples items:

I tested on the server through a Telnet session and it works great when I use the command "helo" and test email internal addresses.  When I try to input the "rcpt to" as a Yahoo email address, it says "550 5.7.1 Unable to relay"
When I try to use the "ehlo" command, it does not work.  It freezes at "250 CHUNKING" and then says "451 2.7.0 Timeout waiting for client input"

The server having the issue sits on the DMZ and needs to pass through the firewall to get to the Exchange server.  I don't believe the firewall is involved being that I can send internal emails, but I figured it was worth mentioning.