Two users who recently upgraded to Outlook 2010 came to me for help using search. The first user wanted to search for partial words, which is not supported by Instant Search. The other user used Office search (.oss) files to find all mail received between and including two dates in his previous version of Outlook and was having trouble making his search work in Outlook 2010.
Instant Search uses the Windows Desktop Search engine, and is much faster than Find. Instant search can also search all message stores in the profile; while Find (and Advanced Find) is limited to a single message store.
However, Instant search can't do a partial word search (bert finds Bertha but not Robert). Advanced Find (using the Advanced tab) will do partial word searches. Unfortunately, you are limited to searching one field, since different fields use the AND operator in Advanced Find.
Instant search can do date-inclusive searches (11/1/2011..11/15/2011 finds all items between and including both dates) but Advanced Find's "between" searches between dates. In the earlier example, the results would include mail up to 11/14, not 11/15. The obvious answer is to adjust the dates, but this has the potential to create confusion. Using "on or before" along with "on or after" results in an OR search, which returns everything. A better option is the Query Builder with "on or before" and "on or after" queries AND'd together.
Query Builder is a hidden feature of Advanced Find and is enabled by adding a value to the registry. It allows users to create complicated queries using AND and OR operators. Once enabled, it works with all uses of the Filter dialog, including custom views, Search folders, and Advanced Find.
See Using Query Builder for instructions to enable it in Outlook 2002 and up.