The Lync client downloads an address book after sign-in. It waits between 0 - 60 minutes before doing this. You can set a regkey to download immediately. If you also exit the client, wipe out galcontacts.db and log on again you will get a new address book. My suggestion is to have a button in the Lync clients under Tools / Options somewhere, that will initiate a new download of the address book - this will come in real handy at troubleshooting address book issues.
Idea No. 392