Based on Lars Careliusson's answer, I made it work by doing the following:
When 'Copy Message URL', append
%3e before and after messageid, as suggested by this article. Here is the Applescript from the article:
tell application "Mail"
set selectedMessages to selection
set theMessage to item 1 of selectedMessages
set messageid to message id of theMessage
-- Make URL (must use URL-encoded values for "<" and ">")
set urlText to "message://" & "%3c" & messageid & "%3e"
Then, add this to your emacs init file:
(concat "open message:" id))))
and the link should be in the following format:
Alternatively, you can wrap
%3e into the
org-add-link-type function and paste the Message ID directly into the org file.