Without the "MAIN_HARDCODE_PRIMARY_HOSTNAME" line in
/etc/exim4/update-exim4.conf.conf a remote server rejected mail coming
from our exim4 server with:

    SMTP error from remote mail server after RCPT TO:<<destination mail server>>
    504 5.5.2 <<hostname>>: Helo command rejected: need fully-qualified hostname

And I expect that many servers require fully-qualified names.  We also
saw a domainless name when talking the server with telnet:

telnet <hostname> smtp
Trying <ip>
Connected to <longname>
Escape character is '^]'.
220 <shortname> ESMTP Exim 4.94.2 Tue, 21 Sep 2021 10:02:08 +0200

The <longname> here is coming from telnet; note the <shortname> in exim4's
response.

Our workaround is to append

MAIN_HARDCODE_PRIMARY_HOSTNAME=<longname>

to /etc/exim4/update-exim4.conf.conf.  Calling "update-exim4.conf"
then reports

undocumented line REMOTE_SMTP_HELO_DATA=<longname>
/etc/exim4/update-exim4.conf.conf, generating exim macro

but it still works (e.g., exim4 now announced itself with the
longname).  In the Debian 9 configuration we had

REMOTE_SMTP_HELO_DATA=<longname>

in /etc/exim4/update-exim4.conf.conf, and I think that this was as a
workaround for the same problem.  But that no longer works in Debian 11.

There is bug report #760278
<https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=760278>, which
seems to be about the same issue.  This bug ended with someone
suggesting that someone else take this upstream (but that upstream may
have been libnss-myhostname).  However, given that this is a
configuration issue (at least it can be configured away, or so it
seems), and given that Debian is the source for update-exim4.conf, it
seems to me that Debian is the right address for reporting this bug.

If you think that there is something that should be fixed in upstream
exim4, I would not know what it is, and could not produce a meaningful
bug report for exim4 upstream.  For bug #760278 sending the reporter
upstream has not led to a fix in 7 years.

In the following I have replaced the mail server names with
<longname> and <otherlongname>.

Please check whether your system is correctly configured to find the
host name. Information can be found on
https://wiki.debian.org/PkgExim4UserFAQ#How_does_exim_find_out_its_host_name_to_use_in_HELO.2FEHLO.3F

Please report back about your results.

Greetings
Marc

It's not quite clear to me what you want me to report, but I will try.

We never had a problem of HELO localhost.localdomain, only of HELO
<shortname>.

After commenting out the MAIN_HARDCODE_PRIMARY_HOSTNAME line (and
running update-exim4.conf and service exim4 restart, I got

# exim4 -bP|grep ^primary_hostname
primary_hostname = <shortname>

I then did "apt purge libnss-myhostname" (and again update and
restart) and now the same command produces:

primary_hostname = <longname>

When trying "telnet <hostname> smtp", the mail server identifies itself with
the longname and replies to "helo bla" with

250 <longname> Hello <longname of telnet machine> [<ip>]

So apparently libnss-myhostname bug is at fault.  Looking at bug
report #756224, it has not been fixed in 7 years, so it is unlikely to
be fixed soon, and a conflict between exim4 and libnss-myhostname
seems appropriate.  I don't remember explicitly installing
libnss-myhostname, so it most likely came with some other package;
however, removing it did not lead to other package removals, so I
don't know how it came in.

- anton