This may not be a popular suggestion but here goes.  I use Google Desktop search because of this same issues I was have with Outlook and Live Search.  It just works!