If I had to guess, I would say this problem was introduced when the new rate module was released for USPS

USPS Module for Zen Cart v1.3.x thru v1.6
* USPS RateV4 Intl RateV2 - January 28, 2013 Updates to: July 28, 2013 Version J