"no Shipping Option" For Random Customers

We have version 3 CS Cart Pro.

Every now and then we will get a call from a customer who tells us that our store says there is no shipping options for their location. We use Fedex real-time and all US states are covered.



Through the admin I can use the “act on behalf of” feature and it works every time. However the customer tells us that the cart says there is no shipping option. It is random and not narrowed down to a state or zip. It doesn't seem to be affected by the Ship-To or Bill-To address.



Has anyone else had this problem? Any thoughts?

Have you read this KB article: