I've been trying to get Contact Form 7 to work for days (current version installed from WordPress.org 9/6/13 - my site uses WordPress 3.6).
I have learned some of the issues have had to do with requirements by my host, DreamHost - I needed to do what ferreste describes above, but not just with the From address but also the To in the CF7 settings. Each of these addresses have to be email accounts associated with domains that live on a Dreamhost server. This is, i believe, an anti-spoofing measure on the part of DreamHost.
After I made this change to CF7 6 days ago, the form worked for a couple of days. Then 4 days ago i changed the perceived url of this WordPress site to be the root AND around this same time Dreamhost's mail server went down. DreamHost support tells me today 9/12/13 that the mail server is back up and fine, but messages do not appear in my client's email.
Through this entire time beginning with the initial problems last week, CF7 always gives the green SENT message each time - the messages just don't make it to my client's mailbox. EXCEPT when I tried the Qmail fix described above by Jack96161: I copied that code into class-phpmailer.php and uploaded it, but when I tried to send a message, CF7 went into some kind of infinite loop, the circling arrows beside the Submit button kept on and on. I never saw that happen before. So i've re uploaded the original phpmailer file again.
I believe that the problem is not CF7, but how it is working with the Dreamhost server - and I am corresponding with DreamHost support, but so far, to no avail.
I am at my wit's end about this problem and am on the verge of just inserting an email link on my client's Contact page - who is desperate for her website contact page to start working.
Thanks to anyone out there for any good ideas...