I had the same problem with a site hosted with Dreamhost. They told me that their mail servers wouldn’t send a message like this unless the ‘From’ email was using the same domain extension as the site it was being sent from.
My example:
Site – siliconprairieconsulting.com
From email – had to be an email with @siliconprairieconsulting.com
Hope that helps!