Contact search Priority

I have an odd problem that seems to only be affecting some of our users. We
have outlook 2003 connected to exchange 2003 on an SBS server. Each user has
3 address books a public folder that was added as an address book the GAL and
their personal contacts. The priority option is set as listed above. if a
user does a search for Brian only users named Brian that are in their
personal contact will show up at first. If you access the public folder the
go back and do an address book search again the contacts from personal
contacts and the public folder will show up.