I have a user that shared her contacts for her boss, giving him full rights as well. The boss could open up the contacts in Outlook, no problem. But when trying to send and email, he couldn’t see the contacts in the address list. After some research, I found out that isn’t officially supported by exchange/outlook. Was hoping 2010 would work for us but was wrong.
Created a Public Folder contact, gave the appropriate users the necessary rights. Then went into the properties of the contact and checked the Show Folder as an e-mail Address Book option. Really is more steps than necessary but at least we got it working. There seems to be a common occurrence of issues with shared calendars and Exchange 2010.