I did the rebuild of the the index two days ago. Yesterday it was still not seeing the searches as it did in Outlook 2007. I'm to the point of rolling several (if not all) of my users back.