To summarize the general problem: Most companies are not on Shopify Plus, and therefore do not have code access to the checkout screen. The lowest-level granularity of Shipping Zones is Province (ie state in the US). So you cannot solve this problem by setting up a shipping zone. Shopify documentation instead refers you to the App marketplace.
The existing apps offer two solutions: 1) inject liquid code to check for zip code at the cart stage (though this can easily be over-ridden by the user in the Checkout), or 2) build a separate Sales Channel that has access to the full-featured Checkout Admin API. If you don't want to build a Sales Channel, but instead want a solution for an individual store, you are directed to use the Storefront API, which is less configurable than the Admin API. And even if you built a custom ShippingCarrier to calculate the delivery cost for a given address, there does not seem to be any way to have a ShippingCarrier deny a particular address. So this rules out any solution that involves redirecting the customer back to the Shopify checkout page via a web url. And if you want to use one of the `checkoutComplete` endpoints, you need to get special "Payment Processing" authorization from Shopify, which takes 7-10 business days.
Given all that, the most reasonable approach seems to be: host a private app that pulls in product data via the Admin API, enforces whatever custom shipping logic you want, processes payment info and taxes (groan), and then sends a copy of the order to Shopify so that all customer data stays in one place. Seems clunky for such a simple thing. Would be interested if someone else has found a solution that I'm missing!