I just installed a new fresh droplet with an Ubuntu 14 server. Then I installed Virtualmin.

And I can send mail but not receive them, the error message is :

<vincent@TheDomain.org>: Host or domain name not found. Name service error for
    name=mail.TheDomain.org type=A: Host not found

Yet I have configurer the DNS :

A       @             45.55.105.XXX 
A        mail.TheDomain.org     45.55.105.XXX
MX       10             mail.TheDomain.org.
TXT      TheDomain.org            v=spf1 a mx ip4:45.55.105.XXX -all

The DNS are the digitalocean DNS ns1.digitalocean.com.

The zone file is :

$ORIGIN TheDomain.org.
$TTL 1800
TheDomain.org. IN SOA ns1.digitalocean.com. hostmaster.TheDomain.org. 1459515870 10800 3600 604800 1800
TheDomain.org. 1800 IN NS ns1.digitalocean.com.
TheDomain.org. 1800 IN NS ns2.digitalocean.com.
TheDomain.org. 1800 IN NS ns3.digitalocean.com.
TheDomain.org. 1800 IN A 45.55.105.XXX
TheDomain.org. 1800 IN MX 10 mail.TheDomain.org.
TheDomain.org.TheDomain.org. 1800 IN TXT v=spf1 a mx ip4:45.55.105.XXX -all
mail.TheDomain.org.TheDomain.org. 1800 IN A 45.55.105.XXX

I didn't modify my /etc/resolv.conf :

# Dynamic resolv.conf(5) file for glibc resolver(3) generated by resolvconf(8)
#     DO NOT EDIT THIS FILE BY HAND -- YOUR CHANGES WILL BE OVERWRITTEN
nameserver 8.8.8.8
nameserver 8.8.4.4

Neither my /etc/hosts

# Your system has configured 'manage_etc_hosts' as True.
# As a result, if you wish for changes to this file to persist
# then you will need to either
# a.) make changes to the master file in /etc/cloud/templates/hosts.tmpl
# b.) change or remove the value of 'manage_etc_hosts' in
#     /etc/cloud/cloud.cfg or cloud-config from user-data
127.0.1.1 ubuntu-512mb-nyc1-01 ubuntu-512mb-nyc1-01
127.0.0.1 localhost

# The following lines are desirable for IPv6 capable hosts
::1 ip6-localhost ip6-loopback
fe00::0 ip6-localnet
ff00::0 ip6-mcastprefix
ff02::1 ip6-allnodes
ff02::2 ip6-allrouters
ff02::3 ip6-allhosts

And from another server, host -t mx TheDomain.org gives :

TheDomain.org mail is handled by 10 mail.TheDomain.org.

So I don't know what to check.

Thanks for the help