I am having a similar problem on one of my Hostgator hosted sites. All of the other sites are working this one just stopped sending out mail.
Mail from Contact Form 7 never arrives but mail sent via the Mail (2) option arrives ok.
Any ideas why this might fail, we have tried re-installing CF7 again but it still fails.
As I say we have many other sites running it and they all work, what can I do to track down what is causing it to fail, but report it has sent the message?