I vaguely remember hitting this message id issue in Google Workspace, and being able to work around it in mail routing configuration.

Saidly I don't remember the specifics, it was something along the lines of not all, but only specific routing features requiring it. Workspace settings are a moving target anyway, so the behavior probably changed more than once since.

I'm not saying it's a good idea to send emails without message id, but i'd also double-check that workspace configuration.