What you are seeing is known as Backscatter. The latest version of Mdaemon has Backscatter protection built into it, but with older versions you can minimise the problem in various ways. One is to add a header to all outgoing messages - say X-BACKSCATTER. This is done using the Content Filter, which is under Security menu. Now when you get a bounce-back you use another Content Filter rule to check for the presence of the X-BACKSCATTER header. If it is there then the original message emanated from your domain. If not then you can safely reject it.
Another thing you can do is to setup an SPF record, this doesn't prevent Backscatter, but at least if the recipient is geared up to check for SPF validity then they can work out whether there's any point in sending you an NDR.
http://www.openspf.org/