Sounds like the domestic zone is catching them first, that happens when it has more in it than one country -- like a whole region or a postcode range left in from before. Which country is actually in your domestic zone, and is anything else listed under it?
Also what did the test address look like. If you only put the country in the shipping calculator and not a full address with postcode, the block checkout can hang on to the last rate it had and you'd have to get through to the payment step to see it switch, but Im not 100% sure on that so someone confirm.
Which Woo version, roughly? Try to check the Locations not covered rate too. That one gets a flat rate copied into it by accident.
Thanks!!