I'm using the Ecclisia theme and have tested the Contact Us page that comes with it and I can send email just fine with it.
I downloaded the Configure SMTP plugin and I am able to test email with it just fine as well.
I'm using Google Mail ( Google Apps )
I dug through the several old posts about this and have tried to update the From: field to a real email address on my domain. I don't have WP supercache activated.
Since email is working with the Contact Us form and the SMTP plugin, I'm thinking it's got to be Contact Form 7 that's not configured correctly.