I got no results (or limited result) returned when searching for e-mail items using Instant Search in Outlook 2007 on Windows Vista.
I tried the suggestions mentioned in the help but to no avail. Then I tried to run the Inbox Repair Tool SCANPST.EXE found on my machine in C:\Program Files\Microsoft Office\Office12
I run it on all PST files and there where errors found in all of the files.
I also run a rebuild of the index just to be sure and it seems like using the Inbox Repair Tool was the solution to the problem.
But the irritating thing is that after a few days the PST got corrupted again. Outlook should really be better at notifying when problems arise like this.