How to avoid that e-mails sent from Host Europe VPS arrive as spam?

When sending e-mails from a Host Europe virtual server (here: Virtual Server Linux), they can arrive in the receipient's spam folder. This depends on the spam filter configuration of course, but did at least happen with a near-default SpamAssassin setup as available on Hostgator Baby Plan as of 2011-10 (valuating a mail with 7.2 points, while another default configuration only counted 0.5 points for that same mail). Some configuration is needed to fix mails being identified as possible spam.

The main problems are shown by these SpamAssassin filtering rules, as indicated in the e-mail headers:

3.2 HELO_DYNAMIC_IPADDR Relay HELO'd using suspicious hostname (IP addr 1)
1.3 RDNS_NONE Delivered to internal network by a host with no rDNS
1.1 FH_HELO_EQ_D_D_D_D Helo is d-d-d-d

The HELO_DYNAMIC_IPADDR rule

This is the main problem in this case, contributing 3.2 points. The SpamAssassin rule descriptions for this rule do not exist on the rule list page. But judging from similar rules, it appears to mean this:

"An untrusted relay uses a hostname in HELO that indicates a dynamically allocated IP address. (So this is different from RDNS_DYNAMIC by referring to the name used in HELO, not the RDNS record, but both can be the same name and that name would trigger both rules then.) Legitimate mail servers would usually be expected to have static allocations. This is determined by checking the hostname given in HELO against a number of inofficial naming conventions. Hostnames that contain sections matching strings such as "dynamic", "dhcp", "adsl" etc. may be matched by this rule, as may names that contain strings of numbers (like lvps165-624-87-23.example.com)."
[Sources used to compile this: SpamAssassin RDNS_DYNAMIC rule page and HELO_DYNAMIC_DHCP rule page, a bug report and a forum thread and the Spamhaus rDNS naming conventions.]

With this interpretation it became clear that the SpamAssassin rule was triggered by the generic hostname used in the virtual server's HELO, as indicated by this mail header (IP addresses are randomized):

from [43.151.120.12] (port=50581 helo=lvps43-151-120-12.dedicated.hosteurope.de)

To fix this, follow these steps:

1. Think of a fully qualified domain name to use as your hostname; for example, server.example.com, but not just example.com. It should be a hostname of a domain you own, as you have to set it up to resolve to your server's IP address.
2. Configure your DNS zone to resolve that FQDN to your server's IP address. You will probably do this with Plesk on the Host Europe server (in Plesk 9: Home -> Domains -> [select domain] -> DNS settings). But maybe you use an external DNS service.
3. Follow the Host Europe instructions to change the virtual server hostname permanently.
4. Ensure that this new hostname is used for HELO when sending mails. For that, just check how your SMTP server application on the virtual server identifies itself when contacting it with telnet on port 25 (for example: telnet 74.161.120.13 25) [source].

The RDNS_DYNAMIC rule

As another common anti-spam technique, many spam filters require that the PTR record for a mail sending host does not look like a dynamic IP address, as these are normally sending mail spam as parts of botnets. The rules for "not looking like a dynamic IP" are just about common practice, see them outlined above in the HELO_DYNAMIC_IPADDR rule section, and also compare the recommendations of Spamhaus: Things like mail.example.com are all ok, but if the PTR contains an IP address it should also contain the keywords "static" and "business" as subdomain levels.

In the Host Europe case, something like 253.44.23.12.lvps.static.hosteurope.de would be the way to go, but the default setting is probably recognized as a spam address. Host Europe knows about this issue, as they say in their FAQ that some e-mail servers will even refuse to accept e-mails from servers that do not have proper RDNS resolution [source]. And there are reports by customers at other hosting companies, reporting that incorrect RDNS setup indeed contributed to problems with mails arriving as spam [example].

Funny enough, the tests do not even get to this point: the RDNS_DYNAMIC rule is not triggered, as the spam assassin protocol shown above seems to indicate that the mail sender host had no RDNS resolution at all (for a reason unknown to us so far). This case triggers the RDNS_NONE rule instead. Anyway, should you run into the RDNS_DYNAMIC rule, here is the fix: to not trigger that rule any more, we will change the RDNS PTR for the Host Europe VPS to something that does not look like from a dynamic IP:

1. Choose a fully qualified domain name as your RDNS name. It may or may not be the same as the server's hostname; for simplicity, I recommend you use the same.
2. If you did chose it to be different from your hostname, make it resolve to the server's IP address. (If it's the same as your hostname, this step is not needed as it was already done above when dealing with the HELO_DYNAMIC_IPADDR rule.)
3. Follow the Host Europe instructions to change the RDNS name in the customer information system.
4. Wait for your changes to become effective. This may take 48 hours or a bit longer to propagate through the whole Internet [source].
5. Check that your RDNS resolution works correctly now. According to [serversupportforum.de thread 124291 post 11 and thread 124324 post 12], do this:
   1. Check resolving from IP address to PTR ("RDNS name"): dig -x 217.79.215.140
   2. Check resolving from the determined PTR back to IP address: dig www.bundestag.de
      Here PTR is www.bundestag.de as an example, and result must be 217.79.215.140 again.

The RDNS_NONE rule

As per the error message this means "Delivered to internal network by a host with no RDNS".

It is not yet clear to me why this happened, or how to fix it. Because the originating host has a valid RDNS resolution even in the case of the Host Europe default setup (then looking like lvps43-151-120-12.dedicated.hosteurope.de). Yet maybe, the error message complains about an intermediate host: the last one before the message was delivered to the recipient's server ("internal network"). In that case, we can't do anything about this.

Other caveats: FCrDNS

Two other anti-spam measures involve FCrDNS verifications, so it's generally advisable to set up RDNS accordingly even though seemingly, these rules were not triggered in the specific case we deal with here:

Use FCrDNS for the mail sending host's IP. Forward Confirmed reverse DNS (FCrDNS) can be used as anti-spam measure by spam filters etc. It means, as per RFC5451: the mail server resolves the IP address of the mail sending host to its RDNS PTR(s), and checks for all these PTRs that they resolve back to the same IP address. Host Europe's servers use RDNS PTR records like lvpsxxx-xxx-xxx-xxx.dedicated.hosteurope.de for this, encoding the IP address, and they pass this test.

Use FCrDNS for the HELO hostname. Finally, yet another anti-spam technique is do to a FCrDNS check on the domain name given by the sending mail server's HELO/EHLO command: resolving the domain name to an IP and the IP back to a domain name(s), and checking if there is a matching one among them. If that fails, it's not reason enough to close the connection (as, even simple name resolution and comparing to the client's IP is not reason enough [source]). However, it is of course possible for spam filters to include it in their rules. To pass this test, one should make the server's hostname the same as the RDNS PTR of the server's IP address; because the hostname is used in the HELO command, as visible in e-mail headers in their source code.