What about using Google Desktop to index your email? I use Gmail (brilliant search) but still download my email into Thunderbird every so often for a backup. Then Google Desktop indexes my Thunderbird mail nicely, and I can find it just by "hitting" Ctrl twice.
gibsonf1, as for importing Outlook email, Gmail can't do it directly, but here's a tool: http://www.marklyon.org/gmail/. Not sure I'd recommend importing "several gigs" though -- Gmail allows up to 2.8GB. I'd probably just switch but keep Outlook and index your old mail with Google Desktop. Gmail is brilliant (as long as you have broadband).