The email provider service can definitely be the issue. I use GoDaddy, or as I call the, GoCrappy. As soon as my contract expires I will be finding another web host and email provider as their services are really bad. So perhaps your email provider service is screwing things up with their servers.