Hi,
Regarding the issue you are faced with, I have two suggestions that you can try.
First, in case the .pst file you are searching on is corrupted, please try to run Scanpst.exe to scan and repair the errors found in the .pst. For Outlook 2003, the location of Scanpst.exe should be:
32-bit Windows C:\Program Files\Common Files\System\MSMAPI\<locale ID>
64-bit Windows C:\Program Files (x86)\Common Files\System\MSMAPI\<locale ID>
Second, we can try to start Outlook with the switch "/cleanfinders", this will remove Search Folders from the Microsoft Exchange server store:
Press Win + R, type "outlook.exe /cleanfinders" in the blank box, press Enter. Check the result if the search works fine.
I hope the information above is helpful.
Regards,
Melon ChenTechNet Community Support