After "clicking for more information", I saw the number of un-indexed items continued to grow! I wasn't able to find a result doing a quick search online, so hopefully this will help others with the same problem. Here's how I resolved it...
Search results may incomplete because items are still being indexed.
Open Vista's control panel and panel type indexing in the search pane, and then click the Indexing Options icon. You'll notice Microsoft Office Outlook under Included Locations. Click it to highlight, and then click the Advanced button.
Next, click the Rebuild button. Answer OK to the warning, "Are you sure you want to rebuild the index?". Wait as the index is rebuilt.
If after rebuilding the index you still get the same error, there is likely corrupt data in your .pst file. See this article for info using the Inbox Repair Tool.
Repair errors by using Scanpst.exe
1. Exit Outlook if it is running.
2. Double-click Scanpst.exe, located at drive:\Program Files\Microsoft Office\OFFICE12.
3. In the Enter the name of the file you want to scan box, enter the name of the .pst or .ost file that you want to check, or click Browse to search for the file.
4. To specify the scan log options, click Options, and then click the option that you want.
5. Click Start.
6. If errors are found after the scan is complete, you will be prompted to start the repair process to fix the errors.
A backup file is created during the repair process. To change the default name or location of this backup file, in the Enter name of backup file box, enter a new name, or click Browse to look for the file that you want to use.
7. Click Repair.