[1] What a nightmare. I have been trying to upload my 7-10 thousand old Outlook emails to GMail for about 2 weeks. Was getting pretty fed up and near enough gave in. It's now in progress but not without major headaches.
Bearing in mind that I wanted to add a Wiki entry for how anyone can do this quite easily, I was wary of some of the console methods and linux solutions as the average Joe Patel would fall over as soon as a procedure said "click on Run and type CMD..."
Firstly, I tried the "set up a pop server at home method". It works but you need to be comfortable with routing and dynamic DNS assigment.
 

Second I tried gExodus and GML (Gmail Loader). No luck there. I'm sure they work but I had trouble with google's SMTP servers - especially in locate one that would let me send more than 5 emails.
 Finally I found the Redirect method. This doesn't keep the date intact but I set up a filter to remind that these emails are OLD. This is the only method that a technical pleb would be able to handle - but it has it's own nightmares.
 

The mail issue is finding an SMTP server that will let you upload so many emails. currently my main Gmail has been locked from sending for 24hours ( :) ), so I had to use another one that I had set up.
I really don't see why Google hasn't got on top of this issue yet. It's the last step to email freedom, web2.0 style.
 

Anyway, The method (and this is a really dirty method, so first lower your expectations):

You need:
1. Outlook (obviously)
2. Outlook Express
3. Thunderbird [2]
4. Thunderbird Redirect Addon [3]
(if you are familiar with Eudora - and you already use it, you can do the redirecting from there)
5. An endless supply of SMTP (sending) servers...

Since Google have a limit on how many messages can be sent through their SMTP and so do most other ISPs, I had to use my ISP's SMTP, yahoo SMTP, google SMTP - moving from one to another as each one was blocked or stopped. I feel like an SMTP Vampire, looking for my next eVictim.
 

So once you have the above tools, import your Outlook to Outlook Express. Then import your Outlook Express into Thunderbird using the Import option in the tools menu:

Why?? Because Microsoft. That one word should explain everything. If you want more, it's because I spent all night importing from Outlook to Thunderbird and all I had was about 30 empty folders. The Outlook Express step clears up any communication problems between Outlook and Thunderbird - worked every time with 3 different email archives.
 

Once you have installed the plugin as per the Mozilla page instructions (link above 'Thunderbird Redirect') and you have imported all your mail, you have to do something a little annoying. You have to setup several accounts in Thunderbird with the corresponding smtp servers. If you can't do this then do a web search for how to setup smtp servers in Thunderbird [4], as it's beyond the scope of this little article.
 

Once you have done that, go to your gmail and setup a filter on the main address (the one you shouldn't be using) - eg: pleb@gmail.com [5] - and tell it to label all the incoming mail as OLD PLEB (but replace pleb with your name/email/whatever). A much neater solution is to use a secondary email that you don't use much to email to and filter the messages from that email as OLD.
 

Highlight some messages in a folder on your Thunderbird, right click on them and click Redirect.

enter the gmail or secondary gmail address you are going to send to and click redirect.
You may get message saying the SMTP server couldn't be reached after a while - that's normal because your riding the server like a bitch. The bars go grey when the emails are sent.
 

When you get a message say something like "you have reached your SMTP sending limited now so bugger off", switch to a different account to send (hence a different SMTP server) and carry on!
 

I'm three days in and nearly finished. GML didn't work for me, neither did gExodus. This has (just about) worked.