Outlook This might be a phishing message and is potentially unsafe

Up till now the hackers have succeeded in breaking each and every protection. So I would say that the Windows Live message is a positive indication, but that one should still use normal caution.

As regarding what you should add to your own emails, see The Sender ID Framework :

Sender ID seeks to verify that every e-mail message originates from the Internet domain from which it claims to have been sent. This is accomplished by checking the address of the server that sent the mail against a registered list of servers that the domain owner has authorized to send e-mail. This verification is automatically performed by the Internet service provider (ISP) or the recipient's mail server before the e-mail message is delivered.

To use SIDF, e-mail senders and domain owners must publish or declare all of the Internet Protocol (IP) addresses used by their outbound e-mail servers, or the IPs authorized to send e-mail on their behalf, in the Domain Name System (DNS). These IPs are included in a Sender Policy Framework (SPF) text file.

In the best case, all this is already taken care of by your ISP.
But it is best to make sure.

In any case, the safety this method gives is based on the DNS system, which we know can be hacked; on the ISP, which we know may be rogue; and on the contents of the email, which can be forged. So Sender ID is surely hackable.

This isn't something that is available in unmodified Exchange, much less Outlook. I have accomplished the exact same thing in two ways.

1) We use IronPort ESA filters/SMTP nodes to accept mail. You can write a rule at this level to do what you are asking before delivering to Exchange. The idea is simple enough and many mail filters will have similar capabilities. Have a mail content rule that triggers if the sender is 'GMS' and body contains serial number 'xyz' (lots of rules, one for each SN); the action is to modify the envelope-sender address to your desired address. Do be wary that you are talking about modifying to an address with a domain that is sounds like you don't control. Depending on where in the process your filter performs sender verification & anti-spoof/spam your alteration of the from address may cause failures to deliver. Just be mindful that there may be additional changes this requires.

2) I have written a custom SMTP Mail Transfer Agent in .Net, my code was to strip & re-route attachments (we didn't want large attachments living in our Exchange server, so the ESA would send emails over a certain size to my MTA that would move the attachments to a file server and insert links to the offloaded files into the message body). You can do the same thing, get a custom MTA that reads the body and changes the from address based upon some lookup information. "If SN matches devices.SN then set From as devices.ContactEmail" type process. You'll need someone to do the coding for you (assuming that isn't in your skillset, if it is, boom, you're all set). Then your MTA just hands the re-written output to the Exchange inbound connector.

No, you can't do this in native Exchange (and especially in Exchange Online, where changing FROM address to non-authoritative domains is a pretty frowned upon thing). But it can be done.