davek.kingserv

I appear to be having a similar problem with a new installation of WordPress and when I raised it with my webhost was advised that they have disabled PHP Mail because of spamming attacks and I have to use SMTP mail instead:

We were facing heavy spamming issues on our shared servers due to phpmail function. As a result the server Ips were frequently getting blocked hampering the server functionality. We had to disable the function as last step to prevent any further performance degradation on server.
Phpmail function is used to send emails through your websites. Please note that if you are sending emails through your webmail or some email client like outlook, thunderbird etc, you will not be affected as webmail or email clients automatically send emails through smtp authentication. However, if you are sending emails through your website and you are using phpmail scripts then you will have to update the scripts and use SMTP authentication
Please download the sample scripts from the URL and integrate the same code under your scripts as per instruction provided. http://edinburgh.theukhost.net/smtp.txt

Might this be a generic issue with spam causing webhosts to protect their servers?