Vi que você marcou a Cisco em nossa pergunta, então acredito que esteja usando telefones Cisco, usei apenas telefones Cisco com o Asterisk, e isso é tudo que poderei abordar em minha resposta.
A primeira coisa que você precisa fazer é adicionar uma entrada de diretório ao seu arquivo SIPDefault.cnf (dentro do diretório TFTP que seu telefone aponta. Aqui está a linha que você precisa adicionar:
directory_url: "http://yourWebsiteOrIp/directory.xml";
O URL deve ser um servidor da Web acessível ao telefone, não ao servidor. Essa linha pode ir a qualquer lugar no arquivo SIPDefault.cnf
O arquivo no servidor deve seguir este formato:
<CiscoIPPhoneDirectory>
<Title>Directory name (will appear in menu)</Title>
<Prompt>Select a person to call</Prompt>
<DirectoryEntry>
<Name>My Phone</Name>
<Telephone>101</Telephone>
</DirectoryEntry>
</CiscoIPPhoneDirectory>
Infelizmente, não sou tão experiente com o Exchange ou Gmail. O que eu posso dizer é que você precisará criar um cron job que irá executar um programa a cada x quantidade de tempo que irá gerar este arquivo XML e colocá-lo no servidor. Toda vez que o telefone acessa o diretório, ele baixará o arquivo XML.
EDIT: Aqui está um link que fornece muitas informações úteis, incluindo uma seção sobre como criar o arquivo XML com PHP: link
Espero que ajude alguns!