Recently no matter what I searched for in my archive.pst file attached to Outlook 2007, I would get no results.
Fix – there is a program called 'scanpst.exe' in program files somewhere (search for it) which is the "Microsoft Office Outlook 2007 Inbox Repair Tool".
Point it at the .pst file and let it run. It told me there were errors and asked if I wanted to repair. I said yes.
Then after it was done, I opened Outlook again, it re-indexed my archive and once that was done I could search again!