RFC2822 suggests to use the FQDN of the machine a message identifier is created on as right hand side (domain-part) of the Message-ID. My computer has no permanent internet-connection and no registered valid FQDN therefore I could not guarantee the uniqueness of the Message-IDs - Somebody else could use "my" freely made-up FQDN at the same time, generating duplicate message-IDs.
I made up my mind and put together this small patch for exim v3.* (it is tested with 3.22, 3.32, 3.33 and 3.34) and this updated version for Exim 4. It was quite easy, I did not do much more than copy the code for message_id_header_text and change the identifier, which should minimize the probability for introducing a new bug. The patch adds a new global option, see below. Philip Hazel does not add new features to exim3 any more, but perhaps this functionality will be included in exim4. - The patch has been submitted.
Update 2002-12-18: This patch or rather a beautiful version by Philip Hazel has been included in Exim 4.11
Type: string, expanded
Default: unset
If this variable is set the string is expanded and used as right hand
side (domain-part) in the Message-ID-header that Exim will create if an
incoming message does not have one. If this is unset the
primary hostname will be used. Only the characters A-Z, a-z, 0-9, . and -
are accepted, all others are replaced by hyphens.
