Comment Re:Yahoo! Mail (Score 2, Informative) 601
After a little testing, now it makes more sense. Message-ID is set by the client. I just sent myself an email by manually doing the smtp (I just made up a message ID and it worked fine).
So it depends where you send it from, not so much the service.
Also, if you really wanted to, you could relay outside of gmail for sending the messages (which would avoid this issue completely), though that might get you flagged as spam (if the domain's mx record doesn't match where the email came from).
