Getting flooded with NDRs of emails we never sent.

Create a rule to move them to another folder.  Otherwise, there's nothing you can do.  

you need a anti-spam solution on your machine.
or enable SMTP filtering on your exchagne SMTP gateway
more suggestions are welcome
thanks.

We have Anti-SPAM installed on the server, but it still lets these through because they are valid non-deliverables. I will not just port them elsewhere because we need legitimate NDRs for when we send mail and the recipient does not get it...

Anti-Spam techniques can be useful against this.  Exchange 2003 with SP2 supports IMF (Intelligent Message Filtering), Black Listing (e.g. SORBS), and Sender ID.  These are accessed via the Exchange Server Manager (ESM), Global Settings > Message Delivery (right-click on it and select Properties).  This includes the Sender Filtering, Recipient Filtering, Connection Filtering (for black listing), Intelligent Message Filtering, and Sender ID filtering.

You can block, via the SMTP adapter's Access tab > Connection button , specific IP addresses (if messages are coming from the same source).

Most NDRs do not include the full text of the original message - only a subject line.  Many subject lines are "common" and virtually impossible to filter out without filtering out good mail as well.

Ark - unfortunately, these are coming from all over the place. They are legit NDRs just sent to the wrong person...

Lee, I expect something to look at the header and see that the original email did not come from our server and thus the bounce-back should not be coming here... Doesnt sound that hard.

Also, the original SPAM uses some fake name that does not go with the mail accounts affected - this would be another way for something to filter it... Problem is, this is beyond Exchange/Outlook as far as I know...  

You can't do that because sometimes people might LEGITIMATELY use a Reply To line and the sending mail server would be different from the one that gets the NDR.

ok you can enable authenticated users and machine accounts for SMTP relay permissions.That helps