Outlook 2007's best feature is the instant search box.
But on a few occasions I've seen that functionality stop working, or start giving incomplete results. The issue appears to be that the search index it uses gets screwed up in some way.
You see, the way an instant search works is that it pre-scans the contents of whatever it will be searching, and then creates an index to work off of. That way it doesn't need to crawl through all your data everytime you want to look for something. This gives very fast (some might say instant) results. But if this index gets corrupted in some way, instant searching won't work correctly.
The fix under vista is to go under control panels, indexing options, advanced. Under troubleshooting, there is an option to re-index selected locations. Click the rebuild button to start the process.
It can take a while to rebuild the index, depending on how big your mailbox is, and what other locations are indexed. But after a bit you should be back to searching without issue.