Why are customers facing checkout issues due to shipping restrictions?

We are having some issues with our checkout - customers are unable to checkout as it states we do not ship to their address.

Shipping not available

Your order cannot be shipped to the selected address. Review your address to ensure it’s correct and try again, or select a different address.

We’ve tried several random UK postcodes and get the same message come up, unless it is a local postcode as we do local delivery from our warehouse.

Can anyone think of why this might be happening? It was working all of last year, then last month it started, then for about 2 weeks was fine, and now it’s not working again - we are now losing sales!

I would first suggest you check the shipping profiles in case you’ve excluded products

Doesn’t mean this is the problem but a good sanity check to rule out first.
https://help.shopify.com/en/manual/shipping/setting-up-and-managing-your-shipping/shipping-profiles/setting-up-shipping-profiles#before-using-shipping-profiles

ProductsAll products not in other profiles

New products are added to this profile.

If everything was working well and suddenly stopped, you should reach out to Shopify Support for assistance.

If you have made any changes to the shipping settings, I recommend checking all the settings once again. I have prepared a checklist for this purpose. It’s called Shopify Checkout Rate Troubleshooting Steps. I hope this helps.