Solução
Para contornar este problema, execute o seguinte comando no Windows PowerShell:
Set-csPresenceManagementState -MaxPublishersPerBatch 1500 -NotificationBatchInterval 2
Resolução
Para resolver esse problema, instale a atualização cumulativa de junho de 2015 6.0.9319.55 para o Microsoft Skype para Empresas Server 2015 (servidor Front-End e servidor Edge).