This thread is incredibly old, but I am posting here to add one more idea... something I have done countless times from Outlook to various Linux email clients: use IMAP.
In short, the steps are as follows:
1. Setup an IMAP mailbox somewhere (maybe even on the Linux box itself);
2. Add the account to both clients (Outlook and Evolution, for example);
3. Copy the messages from Outlook to the IMAP mailbox; and,
4. Copy the messages from the IMAP mailbox to the Linux email client.
Hope this helps.