Given what you tell us it seems you can export a PST giving you a local copy. You can open this locally using Outlook and your messages are there. If you have not worked out how to open it locally with outlook the trick used to be to rename the current *.PST to PST.OLD with outlook closed. When you fire it up again it complains it can't find the PST and lets you enter the path. I could never find any other way of doing this but it has been years (Outlook 2000 days). Once you have finished reverse the process.

Given that you can access your PST with Outlook I would suggest simple Win32::OLE automation of your local Outlook. It may not be fast but should do the trick. You can find most of the code you need at Win32 - M$ Outlook and Perl. The code presented does not get the full headers which you might like to keep. You may find this VB example useful as it gets the headers, body, body as html. Headers and body appended to a text file is more or less standard *nix mailbox format.