Return delivery fails coming from random emails from my domain, afraid of being blacklisted

Question

I have been receiving spam to my email [e-mail], and all of them are return delivery fails from [e-mail] (each delivery fail is from a different random address). I have set [e-mail] as a catch all, so I think this is why I'm receiving all the fails, but I'm not sure whats going on here, how are people/bots using my domain to send out emails? What can I do to stop this? If I don't stop it, will my domain eventually be added to a spam list?

The closest question to mine is this but it does not have an answer. It just tells me to leave it alone, however I don't believe that is helpful.

Here is the source of one of the emails, [e-mail] is a not an address that belongs to my domain though, it doesn't exist.

Received: (qmail 31127 invoked from network); 29 Jun 2012 11:33:31 -0000
Received: from unknown (HELO m1pismtp01-003.prod.mesa1.secureserver.net) ([10.8.12.3])
          (envelope-sender <>)
          by p3plsmtp06-03.prod.phx3.secureserver.net (qmail-1.03) with SMTP
          for <[e-mail]>; 29 Jun 2012 11:33:31 -0000
X-IronPort-Anti-Spam-Result: AmEzAB+S7U/S+LZygWdsb2JhbAAQpj8BkGIBARYmJzgBAQEBAYFXBAFEZwMBAgowAhInCQIWCYVJgisWhQOVIZkdiGyLNxmCVYI8Y4hIhEKIJwGBEpFfgVA
Received: from www.hmjg.co.jp (HELO mail01.hmjg.co.jp) ([210.248.182.114])
  by m1pismtp01-003.prod.mesa1.secureserver.net with ESMTP; 29 Jun 2012 04:33:12 -0700
Received: from mail01.hmjg.co.jp (localhost.localdomain [127.0.0.1])
 by postfix.imss71 (localhost) with ESMTP id EE5326E81D6
 for <[e-mail]>; Fri, 29 Jun 2012 20:33:08 +0900 (JST)
Received: from proxy01.hmjg.co.jp (proxy01.hmjg.co.jp [192.168.1.201])
 by mail01.hmjg.co.jp (localhost) with SMTP id D9F426E818E
 for <[e-mail]>; Fri, 29 Jun 2012 20:33:08 +0900 (JST)
Received: (qmail 8158 invoked for bounce); 29 Jun 2012 20:33:08 +0900
Date: 29 Jun 2012 20:33:08 +0900
From: [e-mail]
To: [e-mail]
Subject: failure notice
Message-Id: <[e-mail]>
X-Nonspam: None

Hi. This is the qmail-send program at proxy01.hmjg.co.jp.
I'm afraid I wasn't able to deliver your message to the following addresses.
This is a permanent error; I've given up. Sorry it didn't work out.

<[e-mail]>:
Sorry, no mailbox here by that name. (#5.1.1)

--- Below this line is a copy of the message.

Return-Path: <[e-mail]>
Received: (qmail 8154 invoked from network); 29 Jun 2012 20:33:08 +0900
Received: from unknown (HELO mail01.hmjg.co.jp) (192.168.1.101)
  by 0 with SMTP; 29 Jun 2012 20:33:08 +0900
Received: from mail01.hmjg.co.jp (localhost.localdomain [127.0.0.1])
 by postfix.imss71 (localhost) with ESMTP id BE79C6E81D6
 for <[e-mail]>; Fri, 29 Jun 2012 20:33:08 +0900 (JST)
Received: from dsldevice.lan (unknown [2.88.2.153])
 by mail01.hmjg.co.jp (localhost) with ESMTP id D4D076E818E
 for <[e-mail]>; Fri, 29 Jun 2012 20:33:07 +0900 (JST)
Message-Id: <20120629143301.594BC9884DD2453419D0C@ALAMIYA-PC>
From: Hai Olson <[e-mail]>
To: tlevesque <[e-mail]>
Reply-To: Robyn Garrett <[e-mail]>
Subject: =?utf-8?B?W0lNU1M6U1BBTV1Vc2VyIHRsZXZlc3F1ZQ==?=
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Date: Fri, 29 Jun 2012 20:33:07 +0900 (JST)
X-TM-AS-Product-Ver: IMSS-7.1.0.1241-6.8.0.1017-19004.006
X-TM-AS-Result: Yes-37.440-7.0-31-1
X-imss-scan-details: Yes-37.440-7.0-31-1

Once you increase the size you will always be loved by ladies. some spam link

D68528CD4C6DD3751F9C09879CC9A97A93DD
BE8480D6015CE7FBC0EFEEA11F6F8EB06BB9
26418FCB70A61CFF8AABE21681063BD0BBBE
9F1C94D3B43CAA293ABE78D660360ADBB993DC
EBEFBDDCECE2CD8CE3CC5C99C09A9A
4796A511EC7EB2D200A2AA43AA92AE34
18F9938296B80EEE3FFE85CD2906274
BC71A9021AF0AEDE23E37FC7F1E51C7
6EA22195FFDD65B74BDC595BD9ED601742
B6E84610AC8344F13D72DCF3044AD28490
E2B6A4D2206FCF8C9371531427CC34F30
897BC49D91126E9C20B82AC711BF9C54

Answer 1

[H]ow are people/bots using my domain to send out emails? What can I do to stop this?

The original spam mail got send from dsldevice.lan (unknown [2.88.2.153]).

Unless that's your IP, there's absolutely nothing you can do to prevent these emails from getting sent. As far as SMTP is concerned, everybody is free to use the sender address he wishes.

If you want prevent other servers from accepting those mails, create a SPF DNS record.

For example, the record

mydomain.com    text = "v=spf1 a mx -all"

will allow sending emails from your domain from the IP(s) of your A and MX records, but no others.

Furthermore, if you digitally sign your emails with DKIM, you can prove that a certain mail was sent by you and not somebody else.

Apart from making others able to distinguish genuine mails from you from forged ones, it should also decrease the chances of your mail getting caught by spam filters.

If I don't stop it, will my domain eventually be added to a spam list?

Probably not. Most blacklists are IP based anyway, and the IP that will be blacklisted is the IP of the server that actually sent out the mail.

Blacklisting sender domains is usually reserved for known spam domains (e.g., cheaprolex.com).

I have set [e-mail] as a catch all, so I think this is why I'm receiving all the fails[...]

What's going on is that hmjg.co.jp is doing it all wrong!

Emails should get rejected while it's getting delivered. Bouncing an email after it was accepted is nonsense, since the sender address can be easily forged (like in this case). They're actually helping the spammers to send their junk to you!

This is known as backscatter, and it's very bad practice. There are blacklists entirely composed of servers that have been set up like this (e.g., Backscatterer).