We had this problem with a few of our recipients as well.
Mainly Comcast users and Century Link to name a few. What the problem is, is that you are sending from (for example) www-data@thisdomain (this will be the machines domain name ie. www-data@WebServer01) — in the header, regardless of who is in the FROM field. Your actual domain in the FROM field is customer_service@yourstoredomain.com. You will need to do one of two things.
If you host the Magento install on your own operating system and you have control of it, you’ll need to change the machines hostname to match that of your web domain name. ie yourwebsite.com.
If that isn’t an option, then you will need to use a Magento plugin like the one you mentioned, and have it log in via SMTP to your email service provider (We use Office365) and send the email from a “real” email address that you have created.
The reason this fails is due to the SPF record on the providers (ie Comcast CenturyLink) not allowing emails from a domain that is other than that which is specified in the header. This is usually to prevent spam etc to their customers. So companies like these simply block or, in some cases, redirect that email back to the user at the originating FROM domain.
If at all possible, the easiest route is going to be to try to change the domain in the header of the email. Hopefully you manage your own operating system so you have control over this. IF not, try to see if your hosting provider will provide you access to a “jailed” area so that you can change said settings.
