Skype does auto search address book/contacts and find who's connected. This fast tracks adoption.
It's kind of clunky that we say Lync integrates with Outlook contacts, but then you have to add lync contacts all over again one by one?!? People expect this to be at least like Skype, so ping each contact to Skype while you're at it. To make things 'usable' you have to make it easy to use from the beginning and show it is intuitive and 'seamlessly' integrated.
There would need to be a way to control the timing of this at the server, because if you on-board 3,000 people at once and it automatically does this at once, it could overload things. Perhaps, stagger with a queue or timing to be off-peak. Also, to save time, it would be good if it searched names/emails/numbers internally first because if that person/number/contact has already been searched by another User in that company, there'd be no use pinging that again. While this is peer-to-peer, it may fast track things at the server level here if you link to the federation directories. http://www.lyncdirectory.com/