Ahh, spelling errors
Had a user raise a ticket because they couldn't send email to an account they had on another domain. Looked in the mail logs and could see they were spelling the domain part of the address incorrectly (it had a double "L" and a single "L" in different places and the user put them in the wrong place). Sent them a log extract to prove this, and they claimed the machine must be changing it somehow...