I wrote a script (batch file, really) that users can run to force a download of the Lync address book.
The Lync address book is generated automatically on the Lync server every 24 hours at 1:30AM, local server time. The address book is then downloaded by the Lync clients in a randomized schedule from 1 to 60 minutes after the client starts up. Lync Server MVP Jeff Schertz wrote about this process in great detail in his post, Updating the Lync 2010 Address Book.
You can use the Update-CsAddressBook cmdlet on the Lync server to force the server to update the address book. You will need to wait 5 minutes for the server to run the update. Look for Lync Server event 21056 from LS Address Book Server to confirm that the address book update has completed, as shown below:
My script sets a GALDownloadInitialDelay key in the registry to force the Lync client to download the address book immediately after signing in. It then enumerates all the SIP_* folders in the C:\Users\username\AppData\Local\Microsoft\Communicator folder and deletes the GalContacts.db and GalContacts.db.idx files which make up the Lync address book.
echo Clearing Lync Address Books…
reg add HKEY_CURRENT_USER\Software\Policies\Microsoft\Communicator -v GALDownloadInitialDelay -t reg_dword -d 0 -f
If %errorlevel%==1 goto Error
dir %LOCALAPPDATA%\Microsoft\Communicator\sip_* /b > list.txt
FOR /F “tokens=1” %%i in (list.txt) do del %LOCALAPPDATA%\Microsoft\Communicator\%%i\gal*.*
echo Sign out of Lync and sign back in to download the current address book.
echo You must run this command from an elevated Command Prompt.
Save the script above as ClearLyncAddressBook.bat and run it from an elevated Command Prompt. Then sign out and back into Lync and the address book will download immediately.