I've also heard that Mozilla Mail under Windows can convert Outlook mailboxes -- but the only solid report I've gotten was that attachments were not converted, so if they matter to you, don't use this method.
There is some documentation on the Ximian Evolution website. I haven't tried this since I don't have a Windows machine anymore. But, here's what they say to do:
Run Mozilla Mail
Go to "File > Import" and select that you wish to import mail from Outlook. When that's done, you're almost there.
I believe that Mozilla stores all its mailboxes as Unix mbox format files, even under Windows. So, all you have to do is transfer those files to your Linux box. You can find them in:
C:/windows/Application Data/Mozilla/Profiles/default/XXX/Mail/imported.mail/, where XXX will be some collection of digits. If there are multiple users on your Windows machine, "default" will instead be your username.
As I mentioned earlier, I've never tried this method, so I don't know how well it works. In particular, the issues raised in section 3.4 probably also apply to this method of conversion.
By the way, the reason that Mozilla can only read Outlook mailboxes under Windows is because it calls a Microsoft DLL to do it.