Question : cannot send mail to yahoo.com from exchange 2003 domain

I am having an issue sending mail from smtp1.riker.com to yahoo.com  My mail is quing up to that domain and bellsouth.net  
This is an example of the NDR's im receiving

> smtp1.riker.com
Name:    smtp1.riker.com
Address:  66.246.139.66

> set q=ptr
> 66.246.139.66
Non-authoritative answer:
66.139.246.66.in-addr.arpa      name = smtp1.riker.com

      [email protected] on 4/4/2008 10:08 AM
            The message cannot be delivered due to a configuration error on the server. Please contact your Administrator.
            66.246.139.66
>_is_blocked.__For_information_see_http://worldnet.att.net/general-info/
bls_info/block_inquiry.html>

      [email protected] on 4/2/2008 3:57 PM
            You do not have permission to send to this recipient.  For assistance, contact your system administrator.
            :
Recipient address rejected: temporarily blocked because of previous errors - retrying too fast. penalty: 30 seconds x 1 retries.>

      [email protected] on 4/1/2008 8:04 AM
            There was a SMTP communication problem with the recipient's email server.  Please contact your system administrator.
            ,dc=net>

I have checked and we are not marked as spammers and reverse DNS is setup correctly.  Any ideas what can be going on.  I have also setup diagnostics logging on the MTA transport and enabled message tracking on my server.  There are 2 backend exchange server and 1 bridgehead server..

The error message im receiving on my mail servers is

Event Type: Error
Event Source: MSExchangeTransport
Event Category: SMTP Protocol
Event ID: 7004

Date: 1/13/2004
Time: 5:23:43 PM
User: N/A
Computer: COMPUTERNAME
Description: This is an SMTP protocol error log for virtual server ID 1, connection #29. The remote host "E2k3server1.contoso.com", responded to the SMTP command "xexch50" with "504 Need to authenticate first ". The full command sent was "XEXCH50 2336 3 ". This will probably cause the connection to fail.

Please help this needs to be resolved ASAP

Answer : cannot send mail to yahoo.com from exchange 2003 domain

Looks like your on the att blacklist, which mxtoobox does not check. http://worldnet.att.net/general-info/bls_info/block_admin.html for removal

Bellsouth.net and Yahoo use graylisting which should delay your mail but not completely block it.

Also are you using multiple SMTP gateways? Be sure to check all your ip. Some blacklists block ip subnets in groups like ???.???.???.???/30