So you are using DDNS and DHCP for your external IP?
The problem sounds as you have gotten a new IP externally, and that hasn't been updated via DDNS. So when someone tries to mail to you, their mailserver gets the wrong IP for the MX record. And when your server is restarted the DDNS record are updated so that incoming mail works some time again.
A solution could be to "Update IP addresses at dynamic DNS services Using ddclient". But this requires to switch DDNS host which I suppose ain't something you'll want to do?
Ref:
http://www.ubuntugeek.com/update-ip-addresses-at-dynamic-dns-services-using-ddclient.html
Are you using No-IP's own DDNS agent?
"
Keep your current IP address in sync with your No-IP host or domain with our Dynamic Update Client (DUC). Our dynamic DNS update client continually checks for IP address changes in the background and automatically updates the DNS at No-IP whenever it changes"
Anyway, to troubleshoot your problem, you can run '
nslookup' from an external machine and see which IP points to your domains MX-record. Do this when the external mail doesn't work. Then compare this IP with your current external IP to see if they are the same. If you give me your domain name I can do a nslookup for you.
Regards, Tobias
