Today my Order Receipt emails started getting "Undelivered Mail Returned to Sender"

Hey, I would love some help with this new problem! Today I have been getting these undelivered mail returned to sender notices on all my order receipts. The emails involved are valid. It appears that its being done because it thinks my order receipt email is spam.

The message I receive is below. I replaced the customer email with xxxxxxxx to protect their info.

Thanks!

>>>>>>>>>>>>>>>>>>>>>>>>

This is the mail system at host u18096086.onlinehome-server.com.

I'm sorry to have to inform you that your message could not
be delivered to one or more recipients. It's attached below.

For further assistance, please send mail to postmaster.

If you do so, please include this problem report. You can
delete your own text from the attached returned message.

The mail system

<xxxxxxxxxxxx@gmail.com>: host
gmail-smtp-in.l.google.com[2607:f8b0:4001:c05::1b] said: 550-5.7.1
[2607:f1c0:80c:7400::7:258e 12] Our system has detected that this
550-5.7.1 message is likely unsolicited mail. To reduce the amount of spam
sent 550-5.7.1 to Gmail, this message has been blocked. Please visit 550
5.7.1 https://support.google.com/mail/answer/188131 for more information.
f97si48517890ioi.143 - gsmtp (in reply to end of DATA command)
Reporting-MTA: dns; u18096086.onlinehome-server.com
X-Postfix-Queue-ID: E761421EAC
X-Postfix-Sender: rfc822; volleyballmanager@oleavers.com
Arrival-Date: Tue, 23 Feb 2016 14:00:54 -0500 (EST)

Final-Recipient: rfc822; xxxxxxxxxxxx@gmail.com
Action: failed
Status: 5.7.1
Remote-MTA: dns; gmail-smtp-in.l.google.com
Diagnostic-Code: smtp; 550-5.7.1 [2607:f1c0:80c:7400::7:258e 12] Our
system has detected that this 550-5.7.1 message is likely unsolicited mail.
To reduce the amount of spam sent 550-5.7.1 to Gmail, this message has been
blocked. Please visit 550 5.7.1
https://support.google.com/mail/answer/188131 for more information.
f97si48517890ioi.143 - gsmtp

We are looking into this. You may get some extra confirmations as we do tests with your account.

Well, it looks like Google just updated their system to be more strict and now it won't accept incoming emails with a FROM address that doesn't match the domain sending the email.

The only solution appears to be to either:
1) Use a @mycafecommerce.com FROM address like: no-reply@mycafecommerce.com
You could use a signed email from to hide it a little like: Volleyball Registration <no-reply@mycafecommerce.com>
2) You could point your main domain to our server so that you can use the domain in your FROM address. It looks like your main domain is just a page with a link to facebook and to your store. If it went to your store you could add a link to facebook on your home page.

Do you think you could explain this a bit differently? I have no idea what you are talking about and I am having the same problem. Sure hope this isn't costing me sales. I have a dreamhost url of dpllconline.com that is DNS only and goes to my commerce store. Based upon what you said here. It looks like all I need to do is to set up new email addresses on dpllconine.com on dreamhost and us those instead of the verizon.net email addresses used previously?
By the way, I've gotten 3 of these back today.

1) Log into your admin.
2) Go to "Settings"
3) Go to each of the email settings for the 5 different emails that the site sends
4) make sure the "FROM" setting for each of the emails comes from your domain. That means if you aren't using a custom domain for your site it should be similar to: "someone@mycafecommerce.com" or if you are using a custom domain you can use any working email address using your domain like: "someone@yourdomain.com"

This has been working great. I followed your advice and used "no-reply@mycafecommerce.com" as my from Email and then used CC to copy in our customer service email.

Thanks!