Woocommerce rejecting orders

I’ve been encountering an issue with some orders over the last week where the customer is proceeding to checkout, entering their address and then they are getting an error message ‘Sorry, we currently cannot ship to your address’. But, all of the customers it has happened to have lived in mainland UK within my UK shipping zone.
After the customers have reported this to me I have gone through and done a test order and it allows me to checkout with their same address, then when I ask the customer to go back and try and checkout again it allows them to proceed as normal with no errors.
Does anyone know why this is happening? Most orders are still going through with no problems, it’s happening on average to every 1 in 10 orders but I am worried this is losing me a lot of business as not all customers are reporting it to me.
All of my plugins are up to date and it’s only been happening for around a week.

Thanks in advance