What exactly should HELO say?

Solution 1:

Cite from RFC 5321 4.1.1.1. Extended HELLO (EHLO) or HELLO (HELO)

The argument field contains the fully-qualified domain name of the SMTP client if one is available.

In other words it should be the FQDN which resolves into the IP address you're sending mail from.

So, if you are sending mail from the IP address 12.34.56.78 and mail.domain.com resolves into 12.34.56.78 (and the DNS PTR for 12.34.56.78 is set to mail.domain.com) you should use mail.domain.com as the parameters for HELO (EHLO).

Solution 2:

Your HELO/EHLO name should be the system's fully-qualified domain name.

In the immortal words of RFC2821 (emphasis added):

These commands are used to identify the SMTP client to the SMTP server. The argument field contains the fully-qualified domain name of the SMTP client if one is available. In situations in which the SMTP client system does not have a meaningful domain name (e.g., when its address is dynamically allocated and no reverse mapping record is available), the client SHOULD send an address literal (see section 4.1.3), optionally followed by information that will help to identify the client system. The SMTP server identifies itself to the SMTP client in the connection greeting reply and in the response to this command.

(the "address literal" is the address in brackets ([192.0.2.1]), or for v6 the address with an IPv6 prefix ([IPv6:fe80::1]))