If you're going to generate a hash, it should be generated across all the required RFC-2822 headers (in addition to the others being discussed), including From:, To:, Subject:, and Date:.   This would help to guarantee the uniqueness of the hash, even if the message-id were to collide.

Second, although you want to use a hashing algorithm that is considered reasonably secure today (e.g., SHA-256), you also want to explicitly include up-front an extension/alternative mechanism, so that in the future when SHA-256 gets thrown onto the same scrapheap as MD5 and SHA-1, you can easily do so.