Does python email generate invalid message-id or does gmail replace valid message-id?

I've created and sent an email using:

import random
alphabet=list('0123456789')
for i in range(26):
    alphabet.append(chr(ord('a') + i))
    alphabet.append(chr(ord('A') + i))

def gen_random_string(length=30):
    return ''.join([alphabet[random.randint(0, len(alphabet) - 1)] for i in range(length)])


from email.message import EmailMessage
import email
import smtplib

msg = EmailMessage()
msg['From'] = my_email
msg['To'] = other_email
msg.set_content(text)
msg['Message-ID'] = email.utils.make_msgid(idstring=gen_random_string(), domain="MY-DOMAIN")

s = smtplib.SMTP('smtp.gmail.com', '587')
s.starttls()
s.login(credentials.login, credentials.password)
s.send_message(msg)
s.quit()

However, Gmail replaced it:

Message-ID: <5e7f5e01.1c69fb81.47373.ca02@mx.google.com>
X-Google-Original-Message-ID: <158540544125.4261.11383854704184591387.n6h3EeqHMnoMCVVSkrgbCqlSyCeTfv@MY-DOMAIN>

According to https://groups.google.com/forum/#!topic/comp.mail.sendmail/gkRdBwka4iw:

Yes, gmail seems to only overwrite the Message ID if you submit it in a wrong format.

In general, I want to get a message-id of the arbitrary sent message (not only from Gmail accounts). I do not understand if the problem is with the python email library or Gmail.

[UPD]: without idstring everything works fine.