As of July 11, I'm getting this from civimail messages, mostly to @gmail.com addresses. The same install has been successfully sending out to the same address list for a long time.
550-5.7.1 [209.15.213.100] Messages missing a valid messageId header are not 550 5.7.1 accepted.
I've turned on the checkbox that generates it, so perhaps problem solved, but is this a policy change from gmail?