Outlook XP Quick Find Public Folders

Running Exchange 2003 with Outlook XP clients.

We recently had to restore a Public Folder called Contacts
and another Public Folder called Prospects.

Both restores went well, with one exception. . .

The quick find feature does not find any entries on most
searches on the restored Contacts folder. The Prospects
folder's quick find runs fine.

Further, on the Contacts folder, advanced find works
perfectly.

Even further, on the Contacts folder, some letters do
return results. For example, if I type 'a', quick find
with successfully find records. . .if I type 'b', quick
find displays no results. About half the letters of the
alphabet are successfully, but in no detectable pattern.

Yet even further, if we do a quick find using known good
letters of the alphabet (eg, 'cas'), the find displays
results, if we use a single letter that is not working,
the quick find fails.

Any suggestions on what could be causing this weirdness
would be very much appreciated. . .otherwise I'm going to
have a very bad birthday.

Thank You
bret