A mensagem de erro parece clara para mim:
O DNS que atende à sua zona deve conter um registro A (ou AAAA se IPv6, mas não um CNAME) igual ao nome do host contido na mensagem de saudação enviada pelo seu servidor SMTP. Essa é uma exigência do RFC 2821.
No seu caso, se o hostname anunciado pelo seu servidor smtp for "mail.exemplo.com", então qualquer pessoa deve ser capaz de resolver mail.exemple.com.
Você pode verificar seus registros DNS usando dig. O resultado deve ser o seguinte:
dig mail.exemple.com A +noall +answer
;; global options: printcmd
mail.exemple.com. 3600 IN A 192.0.2.5
Sua zona DNS e configuração SMTP devem estar configuradas em adequação.