As a wordpress developer sometimes you run across issues that google does not yield an answer; this issue is one of those hence the post here. A site (well my site to be specific) has been running WordPress 4.0 and Contact Form 7 with no issues on a couple different hosting servers. Once I moved it to Media Temple for hosting Contact Form 7 would display this error message upon submission of the forms:
Failed to send your message. Please try later or contact the administrator.
In this case the solution was super easy: Install Easy WPSMTP. Once configured there were no issues with Contact Form 7 sending.