I had the same issue initially, and fellow writer and myITforum'er Rob Stack showed me the light. For my setup, I had Office 2007 Enterprise edition installed on a Vista workstation.
If search in Vista and Outlook doesn't work for you, the following procedure should fix it.
1. Close all Office 2007 or Office 2003 applications.
2. Navigate to Control Panel - Programs and Features.
3. Right-click on Microsoft Office Enterprise 2007 and then click Change.
4. In the Microsoft Office Enterprise 2007 setup dialog box, select Repair and then click Continue.
5. The repair takes around 5 minutes, once it's complete, Navigate to Control Panel - Indexing Options.
6. In the Indexing Options dialog box, click Advanced.
7. Click Continue to get past the User Account Control dialog box.
8. In the Advanced Options dialog box, Click Rebuild to start rebuilding the Vista and office index.
9. Close all Dialog boxes.
Depending on how much you have on your disks and how much you have in your email, it could take quite a few hours to index all of your files.