Question : Returned Email Not Sent By Us

We are getting a lot of returned email like so:
--Start--
The attached message had PERMANENT fatal delivery errors!

After one or more unsuccessful delivery attempts the attached message has been removed from the mail queue on this server.  The number and frequency of delivery attempts are determined by local configuration parameters.

YOUR MESSAGE WAS NOT DELIVERED TO ONE OR MORE RECIPIENTS!

Failed address: [email protected]

: Message contains [1] file attachments


No virus found in this incoming message.
Checked by AVG.
Version: 7.5.518 / Virus Database: 269.21.7/1323 - Release Date: 10/03/2008 11:07 AM

--End--

The following is an example from the MDaemon SMTP (out) log file:

--Start--

Wed 2008-03-12 12:13:49: ----------
Wed 2008-03-12 12:17:50: Session 1572; child 1
Wed 2008-03-12 12:17:48: Parsing Message eq\pd50000014897.msg>
Wed 2008-03-12 12:17:48: From:
Wed 2008-03-12 12:17:48: To: [email protected]
Wed 2008-03-12 12:17:48: Subject: ¢ºIÀúIÀÌIÀ²II·ÐI507385
Wed 2008-03-12 12:17:48: Message-ID:
Wed 2008-03-12 12:17:48: MX-record resolution of [nate.com] in progress (DNS Server: 192.168.100.250)...
Wed 2008-03-12 12:17:49: *  P=010 D=nate.com TTL=(5) MX=[smtp.nate.com] {203.226.255.61}
Wed 2008-03-12 12:17:49: Attempting MX: P=010 D=nate.com TTL=(5) MX=[smtp.nate.com] {203.226.255.61}
Wed 2008-03-12 12:17:49: Attempting SMTP connection to [203.226.255.61 : 25]
Wed 2008-03-12 12:17:49: Waiting for socket connection...
Wed 2008-03-12 12:17:49: Socket connection established (192.168.100.250 : 3214 -> 203.226.255.61 : 25)
Wed 2008-03-12 12:17:49: Waiting for protocol initiation...
Wed 2008-03-12 12:17:49: <-- 220 mta7.natemail.com ESMTP ARGUS Alpha 0.0.1 is ready to Serve.
Wed 2008-03-12 12:17:49: --> EHLO
Wed 2008-03-12 12:17:49: <-- 250-mta7.natemail.com
Wed 2008-03-12 12:17:49: <-- 250-8BITMIME
Wed 2008-03-12 12:17:49: <-- 250-PIPELINING
Wed 2008-03-12 12:17:49: <-- 250-HELP
Wed 2008-03-12 12:17:49: <-- 250-AUTH CRAM-MD5 DIGEST-MD5 PLAIN
Wed 2008-03-12 12:17:49: <-- 250-DELIVERBY 300
Wed 2008-03-12 12:17:49: <-- 250 SIZE 20971520
Wed 2008-03-12 12:17:49: --> MAIL From: SIZE=1267
Wed 2008-03-12 12:17:49: <-- 250 MAIL FROM:OK
Wed 2008-03-12 12:17:49: --> RCPT To:
Wed 2008-03-12 12:17:50: <-- 250 RCPT TO: OK
Wed 2008-03-12 12:17:50: --> DATA
Wed 2008-03-12 12:17:50: <-- 354 Start mail input; end with .
Wed 2008-03-12 12:17:50: Sending eq\pd50000014897.msg> to [203.226.255.61]
Wed 2008-03-12 12:17:50: Transfer Complete.
Wed 2008-03-12 12:17:50: <-- 541 5.6.0 Your message was rejected by PATTERN FILTER
Wed 2008-03-12 12:17:50: Socket connection closed by the other side (how rude!)
Wed 2008-03-12 12:17:50: SMTP session successful (Bytes in/out: 386/1385)
Wed 2008-03-12 12:17:50: ----------

--End--

About 10 emails are sent every 4 minutes all to the same domain @nate.com but with seemingly random user names i.e [email protected], [email protected] etc etc

We all have up to date virus definitions and all of us have had a full virus scan all coming up empty.

Any ideas where to look for a solution?

Answer : Returned Email Not Sent By Us

Your not an open relay, this is a reverse DNS attack, please ensure you have recipient verification turned on in the smtp server settings.

http://www.experts-exchange.com/Software/Internet_Email/Email/Anti_Spam/Q_22938640.html

You could also blacklist that domain in your smtp server so it is never allowed to send/create a connection with nate.com. Nate.com is some korean company I'm sure you'll never need to contact.

Hope this helps!