Se você estiver se referindo ao preenchimento automático do Outlook (e não à lista de endereços real), cada usuário precisará excluir a entrada em questão do cache de preenchimento automático do Outlook (também chamado de cache de apelidos). O artigo a seguir é para o Outlook 2003, mas é relevante para todas as versões do Outlook de volta para pelo menos o Outlook 2000 até o Outlook 2010 (até onde eu saiba).