Fui informado de que isso não era um problema com a máquina. o usuário estava adicionando contatos à pasta "Contatos" errada no outlook ... isso significava que eles não estavam na pasta "Contatos do Lync", portanto, não estavam atualizando no Lync. Foi-me dito que os contactos estavam a ser adicionados correctamente, pelo que isto foi completamente ignorado no meu processo de resolução de problemas ... De qualquer forma, está resolvido, obrigado por todos os comentários.