Smart Host Problem

We currently can't send email to a certain domain, but they can send mail to use. When we try to email them it gets bounced back. I telneted directly to port 25 on their outside IP address, and was able to send a message to them. To test things out more Time Warner told us one of their email servers and to use it. First I set up an Outlook 2000 client to use Time Warner as its outgoing email IP. That worked. The next thing I tried was in Exchange System Manager under Servers -> SMTP -> Default SMTP Virtual Server, was to set up Time Warners Email server as a smarthost. That didn't help anything. The next thing I did was under Connectors I set up an SMTP connector and put Time Warners Email server as a Smart Host and on the addresses tab put in the domain of the place we can't email. That didn't work either. What else could I be missing?? Also, when I telnet to port 25 on my email server from the outside I get a bunch of weird garbage thats this "220 **********************************************************0*2***************
***************200**20*2******0*00
helo
500 5.3.3 Unrecognized command
"
Whats up with that???

The Telnet reponse sounds troublesome. Can you post a screen cap of the cmd window for clarification?

Thats basically it for the Mail Servers Host greeting. Do you know how to change that?? Also, just to give more info my domain is musowls.org and I went to www.dnsreport.com and put in my domain and found a couple of problems one being an SPF record and heres the NDR I get when I send email to the domain that bounces back

(The name is censored)

The following recipient(s) could not be reached:

ml*#(@stmarysschool.org on 11/4/2004 9:37 PM
The e-mail system was unable to deliver the message, but did not report a specific reason. Check the address and try again. If it still fails, contact your system administrator.
< barracuda.stmarysschool.org #5.0.0 X-Spam-Firewall; host 172.16.0.2[172.16.0.2] said: 553 Bad parameters to MAIL command. (in reply to MAIL FROM command)>

Yeah thats interesting I get the same response almost like their is some encryption or something. I don't know the reason(s), I'm pretty new to exchange myself

With the NDR, it looks like their filtering is rejecting you.