I was running 1.38a when this issue started (probably a month or two ago). I upgraded to 1.39h and this issue still happens.

I only use USPS for International Shipping.

1) I have a created a Zone Definition which restricts the International countries I will ship to. Within the zone each country is setup such as "United Kingdom" and "All Zones".

2) The USPS shipping module is configured for production, with my WebTool user ID, and set to use the defined Zone definition.

3) All packages are machinable, All domestic shipping options are turned off. Only the following International options are enabled: "Global Express Non-Doc Non-Rect", "Express Mail Int", "Priority Mail International", "First-Class Mail Int"

To test:

1) I add a product to the cart without logging in.
2) Click "Estimated Shipping" button.
-- Set "Country" to "United Kingdom".
-- Enter in "London" for town.
-- Enter postal code "IG8 7EX".
-- Click Update.

The display updates with:

"Shipping quotes are based on the address information you selected: London IG8 7EX United Kingdom"

However, no options are actually listed.