I found lots of article on how to do this in Outlook 2003, but it took a while to find this one WSS 3 Search Index Rebuild - Outlook by the sound
The conspiracy theorist in me has to question why it is not so much easier to index the most important file format on the web.