Like Lync 2010, Lync 2013 has a random back-off period before downloading the locally cached address book file. This is to avoid a storm of downloads if a large number of users sign in at the same time.
This is why you may see “Address book synchronizing. Results may not be current.”
Also like 2010, you can set a registry key to override this behaviour and have the client download the file on sign in. The key has moved slightly in 2013.
To add the key, run the following from Run/PowerShell as administrator:
reg add HKLM\Software\Policies\Microsoft\Office\15.0\Lync /v GalDownloadInitialDelay /t REG_DWORD /d 0 /f
The location of the cached files has also changed, it is now
GalContacts.db and GalContacts.db.idx are the files you are looking for to show the address book has downloaded
You now see “no matches” rather than a warning about results not being current.