dstrathman--Outlook uses the same indexing as Windows. There are settings to limit the files/folders indexed . But you can also index everything. And there are settings in Outlook to limit the files/folders searched.
So I am not sure I understand your last question. When you run a search after only a partial indexing you should eventually find all the items you look for--at least in the files/folders chosen. It will just take longer. (There is also the option to search All Mail at the bottom of the Search results window.)
Perhaps this reference will help
http://office.microsoft.com/en-us/outlook-help/find-a-message-or-item-by-using-instant-search-HA001230585.aspx
