I've run into the same situation. If the target email is the same domain as the website, it "sends" just fine, but it bounces. I don't think the problem is specific to Contact Form 7 (although I started there too) because my admin email was not working either. When I change all target emails to my yahoo address, everything works fine.
In my case, we use a MS Exchange Server for email at our company. Emails with my domain name sent from my WordPress site do not "escape" the web host (where my blog is). The webhost confirmed the email traffic on their server log. They tried a few solutions including automatic forwarding, but this resulted in an endless loop.
My current workaround is a "mail plus" account at Yahoo. I make that address my target address. For $20 a year they'll automatically forward everything to a domain name address. But I'd like to find a better and more direct solution. I have 4 different forms that were supposed to have different targets. Still, managing the subject line makes them easy to disseminate when they arrive.
Thanks for posting. Nice to have company!