The CBL attempts to detect compromised machines in a number of ways based upon the email that the CBL's mail servers receive.
During this it tries distinguish whether the connections represent real mail servers by ensuring that each connection is claiming a plausible name for itself (via SMTP HELO), and not listing any IP that corresponds to a real mail server (or several mail servers if the IP address is a NAT firewall with multiple mail servers behind it).
In this particular case, the detection is that of a pattern that is heavily used in spam. Furthermore, it is a violation of RFC2821/RFC5321, which defines the SMTP protocol. In certain very rare circumstances, it's an improperly configured server that simply needs to be fixed.
Entirely aside from the CBL, even if it's merely a simple misconfiguration, it is in your best interests to fix this, because many popular spam filters will outright reject email carrying such glaringly obvious RFC2821 violations.
One way of testing whether your mail server is misconfigured is to follow the the helo testing procedure..
Please don't contact us and say "but our mail server software isn't doing it". It may not be, but SOMETHING at the listed IP IS.
If the HELO you see from helocheck is a fully qualified domain name, and you have NOT already done something to fix it, then something other than your mail server is attempting to send email. More than likely a virus/spam trojan, but possibly something like fetchmail, Perl's Net::SMTP or Checkuser modules etc.
If you are running Linux, and/or you're using certain Perl SMTP modules, and/or using fetchmail, there is a good probability that this is a simple configuration problem - the HELO is often "localhost" or "localhost.domain" or "smtp". In these cases, please pay special attention to the remaining paragraphs in order to prevent the IP listing again:
If the mail server in question is an older Linux or UNIX server (especially older sendmails), please check the software's configuration to ensure that it's identifying itself properly. If it uses "localhost" or some variant, change it to be the fully qualified domain name of the server.
With Linux, the problem often appears to be due to the odd way that sendmail determines its own name and an interaction with how the /etc/hosts file is created by the system install procedures. The most straightforward way to fix this is to set the Dw or Dj macros in sendmail.cf (or sendmail.m4). Read this for detailed instructions on how to do this.
It is also reported that removing the "localhost.localdomain" string from the "127.0.0.1" line in /etc/hosts will fix this too, but this is untested.
With Net::SMTP or any module using it, you'll want to insert a "hello" setting in the new().
The Perl "CheckUser" module defaults to improper "HELO" and "MAIL FROM" strings: "localhost.localdomain" and "check@user.com" respectively. The former is illegal, the latter impersonates user.com - they probably don't like that. [Besides, by not using your own domain, some spam filters will lie to your RCPT TO.] You will need to change $Helo_Domain = to be "<DNS name of your server>" and change $Sender_Addr to be something in _your_ domain (ie: "check@<mydomain>").
With the "sendemail" package, the HELO sometimes defaults to "localhost". To correct, find this code (you have probably already adjusted it somewhat):
my %conf = (
## General
"programName" => $0, ## The name of this program
"version" => '1.54', ## The version of this program
"authorName" => 'Brandon Zehm', ## Author's Name
"authorEmail" => 'caspian@dotconf.net', ## Author's Email Address
"timezone" => '+0000 (GMT)', ## We always use +0000 for the time zone
"hostname" => 'localhost', ## Used in printmsg() for all output, and in SMTP EHLO.
[...]
and change 'localhost', to the fully qualified hostname for your
computer.
The PHP Net_SMTP class will also default to using a HELO of 'localhost' unless a different value is passed to the constructor.
If you're using fetchmail: older versions of fetchmail (eg: 6.2.5) almost always use "localhost". The latest version (as of 2006/02/22 is 6.3.2) will use "localhost" if the gethostname() function fails. You should upgrade to the latest version, and make sure that gethostname() returns the fully qualified domain name of your machine - which will probably involve mucking about with /etc/hosts and sethostname/setdomainname. If all else fails, hack the source, recompile and reinstall.
Apparently the "MXLookup" plugin for SpamPal helos as localhost. Turn it off until you can get a fixed version. It is unknown as yet whether a fixed version is available.
If you are running the "Voltage SecureMail" appliance/gateway, it has some issues with its default configuration. Contact the vendor for instructions on how to fix it.
If the mail server in question is Windows-based, it's somewhat more likely to be a spamware trojan, but it could also be a machine using a windows node name (eg: "smtp"), rather than DNS name (eg: example.com)
After making corrections to your mail server configuration, retest it by following the "Testing HELO configuration" instructions above.
If this IP address is a NAT or PAT firewall or gateway, you should also follow the configuration recommendations described here
If the IP relists after fixing this problem, you ALSO have a spam proxy or similar malware problem to track down.