Now that Google has spoiled us with archive-and-search-everything email, I've run into issues with my enormous work inbox. I have mimicked by gmail setup in Outlook with the aid of the fantastic search tool Lookout.
Lookout was acquired by MS a few years ago but was apparantly discarded. More on that from Joel Spolsky. The original author clearly explained how to obtain and configure Lookout for Outlook 2007.
If you're stuck with Outlook, consider this free tool to make searches quick and easy.
One final tip: if you are using Outlook 2007 and hate that annoying "Click here to enable lame instant search" nag bar, fear not. This is how to disable it:
- Tools > Options > Other > Advanced Options
- Uncheck "Show prompts to enable lame InstantSearch"