I have a similar problem, because the system does not chose any more the shipping zone with regard to the delivery address. I mean it worked, but now not any more. I was confused and deleted all Shipping methods for other countries and I configured them as on picture. But this did not work. The clients delivery address was registered separately from order.
Now I tried it with a different older clients address. Also with older addresses it does not work any more.
So there must be something wrong in my configuration?
Or may be it happened since the last update we got during the last days? It seems that the problem started around yearchange.
Desperately tried setting override tax zone Germany but does not change the habit.