have you checked if your isp is maybe blocking it? Maybe they weren't before but now have changed there conditions or something like that.
How have you set up the DNS records? Has something possibly changed here that could be causing this issue? Im guessing your Public IP Address and Private IP addresses have not changed aswell right?
Check these (I dont know what OS you are using so may have to change these commands)
im guessing you have checked the MX records using dig MX yourdomain.com