I have Outlook 2007 with the same indexing issue. Go to Tools|Options|Search, then UNcheck the Outlook and Archive, click OK, then exit Outlook. Restart Outlook and do the same but this time CHECK Outlook and Archive, then OK. Exit Outlook one more time, then restart Outlook. May take Outlook some time to finish the re-indexing. This worked for me. Good luck.