501 Domain must resolve - can't find the problem

I am using an Exchange Server 2003.
When sending to some specific servers, I get the error:
There was a SMTP communication problem with the recipient's email server.  Please contact your system administrator.
            <mail.fire-development.com #5.5.0 smtp;501 Domain must resolve>

I don't understand it, because in my opinion I considered everything:
mail.fire-development.com resolves to 78.47.177.236
78.47.177.236 resolves to mail.fire-development.com (RDNS)
There also exists an SPF entry for my domain which is accepted by a great german ISP (1&1).
But still, I get that error for one specific mail server.
When I connect to that server directly via telnet, I say
EHLO mail.fire-development.com
and receive as anser:
Hello mail.fire-development.com (may be forged), pleased to meet you
And after sending the MAIL FROM command, it closes the connection and says "Domain must resolve"

Here is the header of a mail I sent to the big german ISP:
Return-Path: <d.hilgarth@fire-development.com>
Delivery-Date: Fri, 16 Nov 2007 11:41:21 +0100
Received-SPF: pass (mxeu19: domain of fire-development.com designates 78.47.177.236 as permitted sender) client-ip=78.47.177.236; envelope-from=d.hilgarth@fire-development.com; helo=mail.fire-development.com;
Received: from mail.fire-development.com (mail.fire-development.com [78.47.177.236])
      by mx.kundenserver.de (node=mxeu19) with ESMTP (Nemesis)
      id 0ML05c-1IsydS2cL9-0000j4 for d.hilgarth@###.de; Fri, 16 Nov 2007 11:41:20 +0100
Subject: sss
Date: Fri, 16 Nov 2007 11:41:17 +0100
Message-ID: <215C90BFF6C79F4797048B9CB9A991530370EE@win2k3-03.intranet.lan>
MIME-Version: 1.0
Content-Type: multipart/alternative;
      boundary="----_=_NextPart_001_01C8283D.38B11F36"
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Content-class: urn:content-classes:message
Thread-Topic: sss
X-MimeOLE: Produced By Microsoft Exchange V6.5.7226.0
Thread-Index: AcgoPTfUQ8Jnw860TZG+YXpyuOMqew==
From: "Daniel Hilgarth" <d.hilgarth@fire-development.com>
To: <d.hilgarth@###.de>
Envelope-To: d.hilgarth@###.de

There you can see, that RDNS works, the connection to the mail server comes from the correct IP address and so on...
I don't know what is still missing, please help

Start Free Trial