The name your server uses for the HELO should preferably be an existing hostname (in DNS that is), with the reverse DNS for that IP being the same name. However, although it has become more customary to check for this relation and refuse mail if:
- you don't send a fully qualified name (missing dots)
- you send their own hostname(s) or their IP
- you send "localhost"
and of course:
- if your greeting doesn't match DNS and/or reverse IP.
A setup-checker (as you probably used) can detect all of this, but it doesn't really matter. Most sites hapily accept all kinds of BS, as http://www.faqs.org/rfcs/rfc2505.html
makes these checks optional (MAY) or doesn't mention them. Rfc2505 mostly caused open relays to vanish. It's outdated, but there's no new standard, let alone a good solution.
Bottomline: try go get /etc/mailname in line with a forward DNS name and preferably with your reverse DNS too. If not, at least change mailname to your current DNS name.