Public Folders are hard to work with

In the outlook 2000 public folders we have a contacts databse. This has about 8000 records in it. When I try to search a record it takes for ever to find an entry. It is not that the search is bogus or the contacts are not entered properly. We are using exchange 5.5.