Hi
I am getting undeliverable reciepts for what look like spam emails coming from my domain. Here is an example:

Your message did not reach some or all of the intended recipients. Subject:Attack your baby, she wants
Sent:02/12/2008 01:45
The following recipient(s) cannot be reached:
blah@blah.com on 02/12/2008 01:45
The message reached the recipient's e-mail system, but delivery was refused. Attempt to resend the message. If it still fails, contact your system administrator.
< server.server.com #5.2.0 SMTP; 550 ######## SPAM EMAIL NOT ACCEPTED ########>

The server listed at the bottom is listed second on the list of mx records for the domain the emails seem to be coming from.
What should I do to get rid of these? Should I be worried etc.

You might not need to worry. These messages might be simple forgeries using a From address that has your domain in it. Check to see if the messages are actually being SENT from your server. Then you have to worry.

Yeah I looked at the message headers and they arent being sent by us (phew!) - the word seems to be 'sit it out' but it realy makes me angry since we are a business that depends on email, and being blacklisted would be apolcalyptic....

Out of interest, why do mail servers relay mail from ISPs that allow spammers? Surely all the spam in the world could be solved by a law that says:

It is illegal for ISPs to allow spammers on their network, or recieve mail from an ISP that allows spammers.

?

Ahem. Welcome to the club.

There are a couple of blacklisting sites. Scan them regularly to see if your host is blacklisted. If it is, appeal immediately.

As far as your legal question... there are some laws that say that, but who's going to enforce indonesian hackers spamming Canadian businesses using a German domain?

edzillion:I know this post is quite old, but just so you know, the spammer most likely forged its reply address using an email address from your domain. Spammers forge reply addresses of legitimate email addresses all the time. Usually they move on to others and you have to wait it out. Hopefully by now you no longer have this issue. Though I do not know if they are targeting an actual email address of yours or sending to a "dummy" email address at your domain: one thing that might help is if you disable your catch all and send the email sent to non-existing accounts to dev/null.

edzillion: Another thing now is spam has moved to botnets, so spam is being sent from so many originating IPs that blocklisting them all is nearly impossible, so this is why mailservers will accept some mail from seemingly spammy ISPs. Sometimes there are blacklists (BLs) that get too blacklist happy and end up blocking huge portions of the Internet, say blocking a /24 over a few spam complaints. A /24 range of IP addresses is 256, so innocent users are in that block. Sometimes it has to be done so that an ISP will even notice, so you always have two sides of the story in minimizing spam. When it gets that unreasonable, mail admins move onto other blacklists to use. Yes, some ISPs definitely do not take care of their spamming issues enough, while others are more responsible. Some BLs I recommend are Spamhaus and CBL.

Spam is considered illegal in many countries around the world, however, catching and prosecuting spammers is extremely difficult, especially since some spammers hide in countries that have government officials who choose not to cooperate with international organizations such as Interpol. Better coordination is taking place, but it is very difficult to prosecute say a Latvian-based spam group that spams shucking pharma from botnets in Brazil to recipients in France.