Remarkably, I ran into this issue when upgrading from wheezy to jessie. My machine runs in a corporate environment, and is the smarthost for some virtual machines, but also has to use a smarthost to deliver SMTP mail outside the company.
When receiving mail from the VM (say, vm.mycompany.com), the mail is bounced back to the VM with this message on my host (host.mycompany.com) (/var/log/exim4/rejectlog) 2015-05-27 16:25:45 H=relay.mycompany.com [x.x.x.x] F=<dfsm...@mycompany.com> rejected RCPT <dfsm...@host.mycompany.com>: relay not permitted The problem can be fixed in dpkg-reconfigure exim4-config -> "Mail Server configuration" by listing the local hostname (host.mycompany.com) in addition to the other local domains accepted (which include mycompany.com). This is in contradiction to the wording on that page. Suggest the wording is changed from "The local hostname (host.mycompany.com) and 'localhost' are always added to the list given here." to something more correct! (E.g., "Add the local hostname here to receive mail on this machine. 'localhost' is automatically added.", assuming localhost is added---which I didn't test.) -- To UNSUBSCRIBE, email to debian-bugs-dist-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org