Desculpe por não ter percebido isso imediatamente, porque esse é o problema:
I've both MX & CNAME records set up for verify.example.com
Os CNAMEs só podem existir como registros únicos e não são combinados com outros registros de recursos. Isso é especificado em RFC 1034 , seção 3.6.2.
A razão pela qual o e-mail quebra especificamente é encontrada na RFC 5321 , seção 5.1:
That domain name, when queried, MUST return at least one address record (e.g., A or AAAA RR) that gives the IP address of the SMTP server to which the message should be directed. Any other response, specifically including a value that will return a CNAME record when queried, lies outside the scope of this Standard. The prohibition on labels in the data that resolve to CNAMEs is discussed in more detail in RFC 2181, Section 10.3.
Quando você alterou o CNAME para um registro A, passou de fazer errado para fazer certo, e é por isso que começou a funcionar.
Por acaso, este é um excelente exemplo do motivo pelo qual ofuscar seu nome de domínio é inútil. Se você tivesse dado o seu nome de domínio real, eu provavelmente teria encontrado o erro apenas verificando sua configuração.