Once you get hooked on integrated search in Outlook 2007 and Vista, it's really frustrating to suddenly be confronted with this notice: "search results may be incomplete because items are still being indexed". And for it to stay that way... for days.
After doing a little research, I finally found how to cure my ailment. And, as is usually the case, it turned out to be something that I did. Vista and Outlook did _exactly_ what I told them to do. The source of my problem actually started with my laptop fan running continuously. One day I found that frustrating as well, and after a little research on that topic, discovered that setting my laptop in Power Saver mode made the fan turn off. Ahh... nice and quiet. And since the laptop seemed to actually perform just as well for most of the things I do (mostly e-mail, I'm a little embarrassed to say), I decided to leave it that way.
What I didn't know was that the search indexer plays nice with your power settings. You probably already know that the indexer only runs in the background while your computer is idle. What was new to me is that the indexer stops running while you are in Power Saver mode! After discovering this, it makes perfect sense to me. In fact, I would probably complain if had been designed differently. I put my laptop back into High Performance mode, and about an hour later, I was completely indexed. It turns out that in order to index e-mail items you need to (1) not be in Power Saver mode, (2) have outlook running, and (3) make sure your computer is not going into Sleep state while idle (that is, the hard drive is still running). Problem solved!
For the next release, I think two nice 'features' would be (1) a suggestion on the index status text that lets you know to check your Power Mode, and (2) a "force indexer to run now" task. Hind sight is, of course, very clear in situations like this.