No results from searching contacts?

A user is complaining that she cannot search another users contacts. When she searches, she gets the no results even though that contact exists. She has delegate permissions (editor permissions for contacts). I tried recreating her mail profile but to no avail, Anyone have suggestions? She’s running Outlook 2007 in conjunction with Exchange 2010. She’s on cached exchange mode.