Rastrear e-mails que "nunca chegaram" é um pesadelo administrativo.
Eu começaria (e terminaria) observando seus logs de e-mail como você já fez: eles mostrarão o servidor para o qual seu sistema entregou a mensagem e se foi entregue com sucesso (nenhum erro no seu log de e-mail) ) está muito bem fora de suas mãos, a menos que você queira ser extremamente generoso e começar a chamar os administradores de email em outros sites.
(ProTip: NÃO incomode a ligação, a menos que exista um relacionamento "mutuamente crítico para os negócios", caso em que seu chefe deve conversar com o chefe para juntar os dois para solucionar o problema.).
Voltar quando eu estava lidando com hospedagem compartilhada / serviços de e-mail Eu costumava dar às pessoas esse clichê padrão quando o e-mail "nunca chegava lá", mas nosso servidor não tinha uma boa razão (tivemos uma entrega sem erros):
Electronic mail is a fundamentally unreliable service based entirely on a "best effort" to get messages to their destination. It relies on the cooperation of every machine that message passes through along the way, and can fail for any number of reasons, or no reason at all. There is no guarantee of delivery with electronic mail.
[COMPANY] has given the delivery of your message our best effort: It was handed off from our server ([OUR_SERVERNAME]) to the server responsible for [RECIPIENT]'s email ([RCPT_SERVERNAME]) at [TIME]. Unfortunately while [OUR_SERVERNAME] went to great lengths to move your message in a timely fashion and ensure [RECIPIENT] would get it we can't vouch for how much effort [RCPT_SERVERNAME] was willing to undertake.
(Eu assumo que nossa equipe de suporte da linha de frente limpou isso para ser um pouco menos detestável antes de enviá-lo ao cliente, já que eu nunca fui demitido por causa disso - eu consegui algumas risadas do novo pessoal de suporte embora: )