Exchange 5.5 - Helo command rejected: need fully-qualified hostname - how do I fix?

Please help!  Getting the following bounce back when sending from our domain to this one:

This message was created automatically by mail delivery software.

A message that you sent could not be delivered to one or more of its
recipients. This is a permanent error. The following address(es) failed:
    SMTP error from remote mailer after RCPT TO:<>:
    host []: 504 <blnatl-TW>:
    Helo command rejected: need fully-qualified hostname

------ This is a copy of the message, including all the headers. ------

Return-path: <>
Received: from [] (
      by blnatl-TW with esmtp id 1DMTi3-0006Dk-DE
      for; Fri, 15 Apr 2005 12:30:23 -0400
Received: by with Internet Mail Service (5.5.2653.19)
      id <GRL44XM0>; Fri, 15 Apr 2005 12:30:33 -0400
Message-ID: <>
From: "Nesmith, Robert" <>
To: 'matthew rose' <>
Subject: RE: Banksy Article
Date: Fri, 15 Apr 2005 12:30:27 -0400
MIME-Version: 1.0
X-Mailer: Internet Mail Service (5.5.2653.19)
Content-Type: text/plain;
Who is Participating?
If your hostname matches up properly then I suspect not, but of course I don't know everything.  I've run into this a few times and have had to ask the ISP for a PTR record.  They are usually pretty good about it if you have a business-class service, but if it is DSL or cable I wish you luck!

From a support artice provided by DeskNow (and edited a bit to fit the question):

I think item 2 is quite likely the one you want to look at first...

This response comes from the remote server.
The cause is typically that that server performs some spam-prevention checks on your server, and decides to reject mail from it.

1) HELO name
when a mail server connects to another on to deliver mail, it 'greets' the other server with its own name. This should correspond to the internet name of the server. Ex. . So a DNS lookup to should return the IP address of your server.
Some mail servers perform this check, and if the HELO name does not correspond to your IP address, they reject your mail.

If you have not configured correctly the hostname in your computer, the HELO name will be wrong, so you would need to correct the computer's hostname (which may be problematic if you have AD, etc.)

2) Reverse DNS record
Some mail servers (most famously AOL) also check that your mail server, as stated in the MX record of your domain, has a "reverse DNS" record, and that it points to your server. The reverse DNS is basically the inverse operation of a DNS lookup: given an IP address, it gives you the internet name.

You cannot setup your reverse DNS record yourself. You need to ask this to your ISP. Simply asking "I need to have the reverse DNS record for my IP to point to the name" should do. (Use the appropriate IP and name). If your ISP cannot give you this service, you have two options:
a) change ISP
b) use SMTP forwarding to send mail through your ISP

jimshockAuthor Commented:
I actually saw this article before I posted but was actually looking for maybe something I could change on Exchange Server...
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

jimshockAuthor Commented:
We have a T1, so I will ask them about it - Thanks Mike!
Actually one other thought - you could configure Exchange to route mail destined for a specific domain out via your ISP's mail relay server (setting it up as a "smart host" for the recipient domain).  I'd have to dig a bit to find the steps, so let me know if you need help on that end of it since I'm out of here for the day...
jimshockAuthor Commented:
Killer -- thanks again, Mike, you have a great one as well!
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.