Suponho que você esteja recebendo e-mails diretamente da Internet por meio de um registro MX que se refere ao seu computador com o Exchange Server (com base em suas declarações re: usando TELNET para executar o SMTP "manualmente"). Se você tiver algum filtro anti-spam / antivírus em vigor, deve duplicar / triplicar a verificação antes de começar a reclamar com os administradores de sistema de terceiros.
Tendo dito isso, o melhor lugar para solucionar isso, em seguida, seria no final do remetente. Se você não conseguir obter tração deles para monitorar o fluxo de e-mails enviados, poderá tentar capturar o tráfego do seu lado, mas é provável que você tenha um palheiro gigantesco para vasculhar.
Os remetentes devem procurar logs do protocolo SMTP ou qualquer sistema de email equivalente ao "Message Tracking" do Exchange (/var/log/mail.log, etc) para descobrir como o servidor configurou uma mensagem com falha (que o enviar usuário deve poder ajudá-los a identificar em seus logs). Supondo que eles estão "perdendo" a mensagem, bloqueando por política, etc, é bobagem que seus servidores não estejam enviando uma notificação de falha na entrega para o usuário que está enviando. O e-mail de saída do Black-holing nunca é a resposta. (Enviar NDRs para o e-mail de entrada, sem dúvida, pode não ser uma ótima idéia. Sim, sim-- eu sei que várias RFCs dizem que você deve ... > suspiro <)
Se os remetentes não puderem ajudá-lo, sua única esperança é, muito provavelmente, capturar o tráfego em sua fronteira e tentar identificar tentativas de conexão (ou a falta delas) de seu servidor de saída. Supondo que você possa obter alguém para enviar uma mensagem no comando (digamos, durante uma chamada telefônica) e supondo que a infra-estrutura de servidor de saída não demora muito para processar a mensagem, você deve conseguir capturar uma conversa SMTP com o servidor do remetente ( ou nada, se nunca chegar até você).
Na verdade, isso não é problema seu, de uma perspectiva técnica. Infelizmente, os usuários e o gerenciamento não entendem a natureza do "faroeste" do e-mail da Internet e frequentemente o veem como uma forma confiável de comunicação. Quando a realidade prova o contrário, eles culpam o sysadmin de e-mail mais próximo, em vez de aceitar isso, não diferentemente do correio postal, não é um sistema confiável.