Hi,
What I would do in your case is set dimensions for the fez products and not the other products.
Then, in the shipping methods for the other products, set a maximum volume setting so that it is inferior to the volume of a fez product.
That way, these shipping methods will only display on the checkout if no fez product is in the cart.
Then, for the fez shipping methods, set a minimum volume setting inferior to the volume of a fez product.
That way, these fez shipping methods will only display on the checkout if at least one fez product is in the cart.
And then keep the zone restrictions like you did. It should work like you want with all that.