[This is now documented here: http://msdn.microsoft.com/en-us/library/bb820947.aspx]
There was a thread a while back in the microsoft.public.win32.programmer.messaging newsgroup about how Outlook 2003's new Unicode MSG files. The big question was how to create one. One poster even went as far as to reverse engineer the MSG format from scratch. Fortunately, there's an easier way, which I just got clearance to publish.
We start with the canonical sample for MSG files:
The key is the OpenIMsgOnIStg function. This function takes a ulFlags parameter. All you need to do to create a Unicode MSG file is to pass MAPI_UNICODE in this parameter. Once you do that, the resulting message will show STORE_UNICODE_OK in it's PR_STORE_SUPPORT_MASK and unicode properties will work.
This flag is supported in this function on Outlook 2003 and higher only.