emails to yahoo, sbcglobal and others not delivering..

Folks -- our emails are not being delivered to the recipient.. HELP. Please see below.. let me know how we can get this resolved..

here is an example:

This message was created automatically by mail delivery software.
A message that you sent has not yet been delivered to one or more of its recipients after more than 24 hours on the queue on x5.bimmertalk.com.

The message identifier is: 1Kb0jn-00074X-DS
The subject of the message is: FW: xxxxxx: Order #40366 notification
The date of the message is: Wed, 3 Sep 2008 18:22:08 -0400

The address to which the message has not yet been delivered is:

xxxxx@usc.edu
Delay reason: SMTP error from remote mail server after RCPT TO:<xxxxx@usc.edu>:
host mx.usc.edu [128.125.253.79]: 450 4.1.8 <info@xxxxxx.net>:
Sender address rejected: Domain not found

No action is required on your part. Delivery attempts will continue for some time, and this warning may be repeated at intervals if the message remains undelivered. Eventually the mail delivery software will give up, and when that happens, the message will be returned to you.
--------------------------------

Here are the headers:

--------------------------------
Return-path: <>
Envelope-to: info@xxxx.net
Delivery-date: Thu, 04 Sep 2008 23:03:02 -0400
Received: from mailnull by x5.bimmertalk.com with local (Exim 4.69)
id 1KbRbC-0002zG-7F
for info@xxxxx.net; Thu, 04 Sep 2008 23:03:02 -0400
Auto-Submitted: auto-replied
From: Mail Delivery System <Mailer-Daemon@x5.bimmertalk.com>
To: info@xxxxx.net
Subject: Warning: message 1Kb0jn-00074X-DS delayed 24 hours
Message-Id: <E1KbRbC-0002zG-7F@x5.bimmertalk.com>
Date: Thu, 04 Sep 2008 23:03:02 -0400

i had similar issues and have since added PTR + SPF records, plus Domain Keys and it seems to have resolved the issues.

I had issues with Yahoo.
I made sure all of my domains had PTR and SPF records plus DomainKeys (such as "whost" stated above).
However, I still had issues with Yahoo.
There are forms you can fill out on Yahoo!'s postmaster website and if you work with them and answer all of their questions with detail, then they may help you out.
It has taken me several different attempts with Yahoo to get them to help me but two months into this and I can now see progress being made.

The downside is, I go through this every few years and my mail server doesn't send spam; I do keep a close eye on things and read logs (the most un-fun part of I.T. work).