Public Folder “Contact” Exhange 2003

Why would the quick “Find Now” in Outlook 2003 stop working when searching a public contact folder? Advanced find does. Creating a brand new folder as a test works. Could there be some corruption? I don’t know how to fix this. There are 7,512 records. Thanks.