Are you doing this?
The recommended method to generate shipping rates is to use the POST /cart/prepare_shipping_rates.json and GET /cart/async_shipping_rates.json endpoints because it might take a while for shipping rates to be returned. The GET /cart/shipping_rates.json endpoint is subject to throttling
Without knowing what calls or frequency you’re making them in perhaps you’re seeing a throttle. See how it goes with the async options and if that yields better results first.