Eu já vi essas mensagens algumas vezes. É gerado pelo Outlook - não pelo servidor. Normalmente, o caso é um livro de endereços offline desatualizado.
Você pode verificar isso no Outlook primeiro criando uma mensagem e, em seguida, selecione o destinatário do catálogo de endereços GAL vs. off-line ou no OWA (simplesmente usando o OWA). Se ambos funcionarem (ambos usam a GAL ativa), ele aponta para o OAB.
Você pode forçar um novo download do catálogo de endereços para tentar corrigi-lo, mas verifique primeiro o servidor BITS. Se isso não estiver sendo executado, você não fará o download do OAB (e, portanto, não será atualizado).