There are a few commercial programs to do this  type of conversion.

UniAccess
       http://www.comaxis.com/ua.htm

Aid4mail
       http://www.aid4mail.com/

Transend
       http://www.transend.com/

You might want to check out the converters available at the following site as well.
       http://www.emailman.com/conversion/#mboxwin

Is there any possibility of converting exported messages to .msg format?  Even a third party converter would suffice (if it's cheap).

 

There is probably a mail converter out there to do this but I just export the messages and change the file extension from CNM to MSG and they'll open just fine in Outlook.  Probably the easiest way is to move them to the new mail folder and then go to the new mail directory and change them.

I'm not sure this is an option for me, as the company I work for has recently bought a product that integrates with Outlook for some email services.  I don't think the program would recognize a MIME file with .msg extension the way Outlook does.  I don't have Outlook, nor do I want it.

I have not found any converters that do not rely on an installed copy of Outlook to do the actual translation.  If you know of one I'm all ears!