I had this problem recently on this site that was really baking my noodle. It turned out to be a mixture of SELinux and reCAPTCHA misconfiguration.
First, check if SELinux allows the web server to send emails from your site:
$ su -
# getsebool httpd_can_sendmail
If the boolean is off, turn it permanently on:
# setsebool -P httpd_can_sendmail 1
Then make sure that reCATCHA is properly set up for the form you are trying to send emails from (Configuration, CAPTCHA module settings, CAPTCHA Points tab). In my case, both needed to be properly configured before I could send emails from my site.