History always repeats itself and sometimes that's good. Here's a second chance to be part of it: tmdtc.com
Locate a message in Gmail with its Message-Id
I recently had to search for a mail delivered to Gmail according to the mail server log, but I couldn't find it immediately.
As I wanted to search the message based on its Message-Id found in the mail server logs, I found this help page. After clicking several checkboxes, it display a form that lets you search your inbox based on the Message-Id. However, looking at the search query generated, it's very simple to do it right from your inbox. Just type this in the search box, replacing $my_message_id by the actual value you're looking for