I have tried to find a similiar situation in the forums about this, but have had no luck. If someone knows how to restrict the free shipping module to work only in that zone, regardless of billing, and if not in that zone, not allow the payment to go through.

Zen Cart 1.3.8a
Database Patch Level: 1.3.8
v1.3.8 [2008-08-17 17:53:10] (Fresh Installation)
v1.3.8 [2008-08-17 17:53:10] (Fresh Installation)

While using FREE SHIPPING! with shipping zone set to custom zone: Continental United States
and
While Payment zones set to custom zone, USA, Mexico, Canada

A customer can purchase product and ship to ANYWHERE in the world for free.

On checkout page, shipping shows:
at the top it shows an overview of shopping cart with shipping at:

Free Shipping: $0.00

below it shows:

Not Available At This Time
Sorry, we are not shipping to your region at this time.
Please contact us for alternate arrangements

But still allows payment to go through as long as their billing address is in the payment zone.