I have Exim configured to remove the hostname portion of the domain on outgoing mail, and yet the hostname is present when the mail gets delivered.

Check the DNS record for your domain. If the MX record points to a CNAME record instead of to an A record, some MTAs (not Exim) are liable to rewrite addresses, changing your domain name to its canonical form, as obtained from the CNAME record.

---