This is Rae from Shopify. Thank you for reaching out about your shipping settings, and welcome to the Shopify Community!
I understand how heavily this is impacting your store, and I'm glad to help look into this further and determine the best way to get this resolved.
As a first step, can you please confirm if every customer who receives this error is based in the same location? Or, are customers from multiple locations receiving this same error? Can you also please provide a few examples of the countries, or geographical locations, that customers are unable to checkout from currently?
When this error appears, it usually has to do with the customer's shipping location not being added to the rates in the 'Shipping' section of your Shopify admin. You mentioned that every address tested is already included in your zones, however, I recommend double checking this to confirm. To do this, please open up your Shopify admin, click on 'Settings > Shipping and delivery', and click 'Manage rates' to open each of your rates to determine if the customer's location is included in any of your zones here. If you find that the customer's location currently doesn't exist in any of your zones, you can add this location by following these steps and editing your shipping rates. Doing this will help resolve the error that's appearing on your checkout, and allow customers to place their orders correctly. Let me know how this goes!
In the meantime though, you mentioned that this issue started occurring several days ago. With this in mind, do you recall making any edits to your shipping rates recently that may have caused this change?
Once I have these details, I'll be glad to assist further!