550 Requested action not taken: mailbox unavailable

I setup a small box with Server 2003 64bit to be used as a webserver and email server for a small school. Real simple stuff for a few users. A simple website and a handful of emails. rDNS and spf records setup and pass every test I found including test at dnsstuff.com.

Email sending to almost every email address (google, hotmail, aol, whatever) works. However, with one domain, I get an bounce back with the error.

550 Requested action not taken: mailbox unavailable

It's another school running Exchange judging from some packet sniffing with WireShark. Every email on this domain I have tried sending to gives this error. The email address is valid as I can send to it from my personal, and gmail account without a problem.

Does anyone know of some anti-spam software that gives an 550 error like the above? What else could this be?

Thanks for any suggestions.

Packet capture of the two servers communicating look like this.

220 <server snip> Microsoft ESMTP MAIL Service, Version: 6.0.3790.3959 ready at  Sat, 2 Oct 2010 12:48:17 -0700 
EHLO <email snip>
250-<server snip> Hello [<ip snip>]
250-TURN
250-SIZE
250-ETRN
250-XXXXXXXXXX
250-DSN
250-ENHANCEDSTATUSCODES
250-8bitmime
250-BINARYMIME
250-XXXXXXXX
250-VRFY
250-X-EXPS GSSAPI NTLM LOGIN
250-X-EXPS=LOGIN
250-AUTH GSSAPI NTLM LOGIN
250-AUTH=LOGIN
250-X-LINK2STATE
250-XXXXXXX
250 OK
MAIL FROM: <email snip>
250 2.1.0 <email snip>....Sender OK
RCPT TO:<email snip>
250 2.1.5 <email snip> 
DATA
354 Start mail input; end with <CRLF>.<CRLF>
<email body here>
.

550 Requested action not taken: mailbox unavailable
QUIT
221 Goodbye

From serverfault Porch

• You might consider making contact with the admins/postmasters of that domain. They may be able to provide more specific details as to what is triggering the rejection by their system(s).

  Porch : I have called around, but that might not be an option. I think they outsourced everything and nobody really knows what is going on. I will keep trying, but I don't have much hope.

  : Another way at approaching this may be to have someone from the other school send a message, so that headers can possibly be analyzed for the identification of the culprit (assuming that their incoming and outgoing email flows take very similar paths).
  From

• You can use telnet to simulate your server. Try to see where in the dialog this comes up. It may give you a clue as to what is happening. Try sending to postmaster@OtherSchool, this mailbox should always be there.

  Porch : From looking at a packet capture, it's right after the my server sends the body of the message to the other server.

  Porch : From looking at a packet capture, it's right after the my server sends the body of the message to the other server.

  Porch : dang. Hit enter twice.

  BillThor : Unless pipelining is enabled, the recipient should have been rejected before the data was sent. It could be a delayed check, delayed rejection, or some sort of spam check. Do you use the FQDN in your hello message. This can trigger some rejections.

  Porch : I do use the FQDN in the hello message. I am suspecting some type of spam filter, but I don't know of any that work this way.

  BillThor : It could be a custom filter, I have custom filter in Exim then SpamAssassin. Looks like it runs at data time. Check what they provide in their initial banner. It may tell you what software you are connecting to. Then again I changed my banner to ESMTP Server ready. Can you send them email from google or elsewhere? They might be limiting who can send them mail. Also check your IP address at one of the sites that check lots of black lists. You might be listed on an obscure list.
  From BillThor