Message-ID is a unique identifier for a digital message, most commonly a globally unique identifier used in email and Usenet newsgroups.
I'd go with that, as it's independent of GMail, guaranteed to be unique, well documented, and used since the dawn of time.
Further: Google commented that X-GM-MSGID could theoretically change.