Had some issues setting up a site developed by other developers. Aaaaaand this is why Gravity Forms is better. But, anyway, the solution was simple enough: http://wordpress.org/support/topic/contact-form-7-not-working-6
Update: Come to find the same issue with Gravity Forms on a Liquid Web VPS. I realized that (duh) this would always be an issue for clients who use a remote mail exchanger, as the server won’t even look outside itself if it thinks the mail exchanger is local. So, the steps for a cPanel host (which is most of my clients):
cPanel->Mail->MX Entry->Choose Domain-> Find MX Record and look for “Email Routing”->Change to Remote Exchanger.
Of course, ONLY do this for sites that aren’t using the web host to collect mail!