I think it is FedEx. Is anything about
FedEx recorded in the Error Log?
Update 1: You can probably use an Order Rule Provider to protect against this...I'd have to experiment to know for sure, but I thinking a rule like, If Rate From "FedEx Ground" equals 0, Cost = Rate From "UPS Ground". I know you don't actually ship via UPS, but the rates are pretty close...certainly closer than 0.00.
Update 2: I confirmed that you can do this (create a simple Order Rule or Package Rule shipping method that encapulates the FedEx rate with a backup). Here is a picture of the one I tried,
http://screencast.com/t/KCNphMhrVo This works because an empty list of rates (such as when FedEx hiccups) is treated as the value 0 in the comparison.
You can also use the same pattern to call FedEx twice (with the hope that the second time will work if the first fails). Normally wrapped rates are cached so that in comparisons like this the carrier is only called once. But if no rates are returned they are not cached. So a rule like...
When Rates From "FedEx Ground" is equal to 0, Cost = Rates From "FedEx Ground" x 1
For all remaining orders, Cost = Rates From "FedEx Ground" x 1
...will actually give you two chances to call FedEx. If the first call works, then those rates are used and you don't have to wait for a second. But if the first call fails, FedEx is called again. Unfortunately, if the second call fails, you will still get 0 shipping.