Comment by citrin_ru

You can argue that you not obligated to use message-id but if you don't use it you should blame only yourself that your messages are not accepted. In requiring message-id I would side with google (though in general I think they anti-spam is too aggressive and lacks ways to report false positives). Full RFC compliance (as in not only MUST but also SHOULD unless you have a very good reason) is the easiest part of making sure your emails will be delivered.