Challenge was announced last week, here: how to get many years' worth of email stored in old Outlook .PST files into an online Gmail account.
Main reason for change: wanting to have email archives searchable and available from any computer, rather than worrying about which .PST is on which machine. They'd also be searchable and usable from mobile devices with Gmail apps -- which I know first-hand includes BlackBerry and Android/Nexus One, and which I believe now includes iPhone and SideKick. Other motives discussed in the original post.
Promising-sounding solution that's not right for me: Google offers its own "Google Email Uploader" (left) available for free download here. It sounds as if it exactly fills the bill: "It uploads email and contacts from desktop email programs (like Microsoft Outlook® ) into your Google Apps mailbox. It preserves information such as sent dates and sender/recipient data, as well as the folder structure used by email programs." Unfortunately, it doesn't work with normal, free Gmail accounts. It requires a different "Google Apps" account. These cost $50 per year (details here), and while that's hardly prohibitive, for the same money I could buy 200 GB of online storage from Google (see here). And this approach would defeat my purpose of concentrating my mail in one, main, existing Gmail account.
Conceptual basis of the real solution. It involves IMAP accounts. If everything about IMAP and POP3 is already obvious to you, skip to the step-by-step list further down. If not, read the next paragraph.
Outlook (and other email handlers) can interact with online email services, like Gmail or Hotmail, in two main ways, via POP3 or IMAP. (There are others, which we'll ignore for now.) Fundamentally, POP3 is a way of collecting messages from Gmail or Hotmail and transferring them to your computer, whereas IMAP is a way of mirroring what's in your online account on your own computer. Here's the practical difference: With a POP3 account, what you do to messages on your own computer has no direct effect on the versions of those messages stored online. You can collect all your Gmail message into Outlook and save or delete them there, but the originals will still be sitting in your Gmail account. But if you've set up an IMAP connection between Outlook and Gmail, what happens to a message in either place affects it in both. If you delete a message in Outlook, it also disappears from Gmail. And if you add a message to an IMAPed Outlook folder, it will also be added to the corresponding Gmail account. That's the key to the .PST -> Gmail transfer.
Step-by-step procedure: This is all you have to do. It's easier than it looks. If you have a lot of messages, the full transfer takes some time -- but it's mainly "the computer is thinking" time, rather than "you have to pay attention" time.
1. Load Outlook, and create a "New Email Account." Procedures vary with different releases of Outlook. For instance, in Outlook 2007 it's Tools / Account Settings / E-mail / New. Give this new account the settings (user name / pw) of the Gmail account in which you want to store your old .PST messages.
2. When setting up this new account, specify it as an IMAP account, not a POP3 account. (That's the choice Outlook will give you.) Note: this can be the same Gmail account that you're already using with Outlook, via a POP3 connection. There's no problem with Outlook having two of its own email accounts addressing the same Gmail account. For years I've collected my Gmail messages into Outlook via POP3. For the transfer, I just created a new IMAP connection to that same account. Outlook happily keeps both of those open at the same time.