I have been struggling with this since we launched in June 2019, and I've finally hit my breaking point.
We ship to the entire USA, and that includes military addresses. Shipping is free across the board.
No matter what I try, I can NOT get Shopify to print shipping labels for these military addresses. I end up copying/pasting the address into a 3rd party software, and the label spits out without issue.
When I enter the customs info, and the package weight, I get rates from USPS. When I click "Buy Shipping", I get a red error that states "The address you're shipping to could not be verified".
I also just started having this issue. A customer of mine is on his 17th order, without a change of address ever, and Shopify will no longer accept his address to create a label. It keeps saying the address could not be verified, despite also being able to get rates. This needs to be fixed as soon as possible!