Your error regarding "domain literals" comes from the configuration of your mailserver. I imagine that this was intentional and you don't ever expect mail to be sent to email@example.com anyway. It is obvious that your mailserver is talking.
Your provider is simultaneously the right and wrong person to verify your records. Assuming you use their servers, what they see is the most up-to-date information. It is likely that older information is cached in other places, or the chain pointing to your server is incomplete -- major domain servers might not be pointing to your nameserver, for example.
To test that the mailserver is acting correctly while the DNS system isn't, I suggest putting a hosts entry on a mailserver and then sending mail from that. Otherwise, do some directed-digging of DNS records:
dig example.com @10.1.2.3. Check for all the different types of records you need along the chain (NS @ a .com server, A and MX at your server...).