Isso acontece com todos os usuários ou com apenas um usuário? Isso acontece quando eles estão enviando para um colega de trabalho específico ou para todos os outros colegas de trabalho? Mais informações sobre suas etapas de solução de problemas ajudariam a restringir uma resposta. No entanto, vou oferecer uma solução desde que vi essa mensagem de erro antes.
Eu tive esse problema com alguns dos meus clientes e foi assim que resolvi:
Eles estão usando o preenchimento automático para selecionar o endereço dos destinatários? Peça-lhes que tentem digitar o email manualmente. Se isso funcionar corretamente, eu excluiria o arquivo .n2k em seu perfil. Às vezes, o arquivo .n2k pode estar corrompido e precisa ser limpo. Vamos esperar que eles não o usem para um catálogo de endereços.
Você não diz qual versão do Windows, mas o arquivo .n2k é armazenado de forma genérica nos seguintes caminhos.
Windows XP:
Drive:\Documents and Settings\Username\Application Data\Microsoft\Outlook
Windows 7:
Drive:\Users\Username\AppData\Roaming\Microsoft\Outlook