The message below is also not sent:
(Your message sent successfully.)
On my site i had this problem.
It seemed to be something to do with using a third party email system, rather than the system used by my hosting company.
Changed to using my website hosting company address (as in the URL) and all is now working fine.
