Supondo que esse seja seu domínio real (pelo qual, muito obrigado), você tem um problema com seu registro MX:
[me@lory ~]$ dig mx fish-thecompany.com
[...]
;; ANSWER SECTION:
fish-thecompany.com. 86313 IN MX 20 mail.fish-thecompany.com.
[me@lory ~]$ dig mail.fish-thecompany.com
[...]
;; ANSWER SECTION:
mail.fish-thecompany.com. 86300 IN CNAME fish-thecompany.com.
fish-thecompany.com. 86300 IN A 109.228.0.95
Mas RFC2181 é muito claro sobre o assunto:
10.3. MX and NS records
The domain name used as the value of a NS resource record, or part of the value of a MX resource record must not be an alias. Not only is the specification clear on this point, but using an alias in either of these positions neither works as well as might be hoped, nor well fulfills the ambition that may have led to this approach. This domain name must have as its value one or more address records. Currently those will be A records, however in the future other record types giving addressing information may be acceptable. It can also have other RRs, but never a CNAME RR.
Meu palpite é que alguns dos seus remetentes estão usando servidores de e-mail que são intolerantes a violações deste RFC específico; no que diz respeito aos seus servidores, você realmente não tem nenhum trocador de e-mail válido. Corrija isso, torne o seu host referenciado por MX um registro A, e isso pode melhorar.