Gerenciado para resolver meu problema, não tenho certeza se ele consertará seu Geoff, mas tente.
Basicamente, as entradas de DNS do site foram gerenciadas externamente. Isso incluiu DNS para o site e email.
O problema surgiu porque meu servidor da web também continha entradas de DNS, portanto, ao enviar e-mails, tentou enviar para seu próprio servidor de e-mail em vez de externo, o endereço de e-mail 'não existia e recebeu essa mensagem.
Espero que isso ajude alguém na mesma posição.