Se você está falando sobre o recurso "auto complete" (que muitas pessoas realmente confundem com um catálogo de endereços), elas são locais e nunca são atualizadas pelo servidor. Embora exista um arquivo no perfil que contenha esses dados e você possa excluí-lo para limpá-lo (e, em versões mais recentes, você pode realçar uma entrada completa automática e clicar em excluir).
Se você está realmente falando sobre a lista de endereços global, então (novamente em versões mais recentes, eu não usei o Outlook 2003 há muito tempo), há uma opção no botão "Enviar / Receber" / menu para fazer o download o "Livro de Endereços". Além disso, o OAB é atualizado em determinados intervalos no servidor, portanto, talvez você queira ir ao servidor e iniciar uma atualização manualmente apenas para ter certeza.