This is often related to the ISP's providing you a dynamic IP address which prevents to use of sending through external mail servers. You can either contact your ISP to ask how to set up their outgoing mail settings, or ask them for a static IP address (which is best)
Alternatively you can host your domain and email on an external server and simply leave the "add to dns" box unchecked from the domain settings page. Doing this will allow you to point your domain to your store, but run your email externally to prevent any SPF problems.
