Exchange Message ID's

I do not believe Exchange enters information for the message store. It would show the server information only if the FQDN for that server has not been changed in the virtual SMTP server properties. The default is server name, but some administrators change it to the FQDN of the exchange site.

You might be able to tell this if you read the RFC that describes the requirements for email headers. I haven't done this (my eyes would cross), but judging from the format of the message ID in the headers, which is basically:
[long complicated alphanumerical string]@server.domain.com

I would have to say that it appears to be a per server generated ID rather than having anything to do with the particular information store. This is basically just a guess, tho, although an educated one...hope it helps!