Just a note for anyone who finds this topic and is still having this problem:
We recently switched to using cookieless authentication, which has resolved the problem permanently for us. Check out the pinned article Introducing cookieless authentication beta with App Bridge for discussion, and there is more information in Shopify’s Authenticate your app using session tokens tutorial.
I hope this helps.