> 2 means some polygons overlap which is fine too

For some use-cases, sure, but not all. One common use-case for zip code polygons is "I have a lat/lng, just give me the zip code, damnit!" Your users might expect that a lat/lng point can have no zip code, but most won't expect that it can have multiple (because no address has multiple zip codes).

At a minimum that leaves you scrambling to explain "well, but it only happens in a few edge cases where a land parcel has multiple mail delivery locations from different postal carriers, and it's super-rare, pinky swear".

> 3 means some zipcodes are excluded from scheme, as one might not be legally allowed to know where a particular unit is.

Another very common use-case for zip code polygons is "I have a zip code, just tell me where it is, damnit!" Maybe they want to estimate shipping distance without hitting the shipper's API.

Part of the problem here is that the AFPO zips do have a physical location for this purpose, which is the facility where mail and parcels are delivered from the USPS to the AFPO. And your users will probably expect you to know that's what they mean. So when you try to explain that "actually an aircraft carrier is constantly moving and we're not allowed to know where it is", they will think you are being pedantic and condescending, and look for someone else to sell them polygons.

But let's say the user actually wants to forecast sales of the new ThingyWidget 3000 by estimating the average weather by customer zip code (by getting the polygon for each zip and the doing a spatial join to weather data). When they do that for the AFPO drop-off point, they're going to get a completely wrong estimate of the weather because the people receiving mail at the AFPO zip are not physically present at that place. So when you explain that "actually that is the physical location of the AFPO facility" they will also think you are being pedantic and condescending, and look for someone else to sell them polygons.

Notice how you're damned if you do and damned if you don't?

Any choice you make for polygonalizing zip codes will be wrong for some use case, and it will be spectacularly wrong for certain edge cases in very intuitive ways that certain users deeply care about and will blame you for.

Which brings me back to the point: You can make a set of polygons for zips which is "good enough" for many use-cases, but ultimately you cannot represent zips as polygons in a way that is suitable for all use cases because, once again, zip codes are not polygons!