There are a couple of things to check initially:
Find your domain's TXT record. This usually appears beside the CNAME record and MX record.
Add the following SPF record to your TXT record
v=spf1 include:shops.shopify.com ~all
There are other issues that could cause your emails go to spam. Those are the first to check.
That's an interesting workaround. How has the response been to the texts requesting customers to add your email to their contact list?
It shouldn't be too complicated to update those two items mentioned.