Many other applications will let you search your email. The user experience is entirely different if the search is fast and is run against the entire body of text.
Running a search against a 500MB store of emails on outlook can take minutes. Indexed search can take seconds or even fractions of a second.
I currently use the "Nelson Email Organizer" with outlook. It provides indexed search, so that I can find a message within seconds. It also creates automatic folders (a kind of standing search) for each correspondent. Indexing makes these operations instantaneous or very quick, so that I no longer need to organize my emails into folders.
If the cost of a search is low to me, I will do it often, changing fundamentally how I organize and retrieve information.
Speed matters. We should be able to Google everything, including our file system. Windows 2000 and XP have a built in indexing service, but Microsoft does little with it (it does a poor job of speeding up the "Find" function.)