Question
The problem only surfaced when sending mail from a particular domain to multiple recipients
Answer
This was due to a very badly fragmented disk. Running a disk defragmenter a couple of times on the disk cleared the problem completely.
Keywords:headers, mail, missing