Fedex publishes rates and is supposed to be bound by them.

Here you go, from http://www.fedex.com/us/service-guide/terms/express-ground/i...:

"Rates and service quotations by our employees and agents are estimates and will be based upon information provided by you, but final rates and service charges may vary from the quotes based upon the characteristics of the shipment actually tendered to us. Any conflict or inconsistency between the FedEx Service Guide and other written or oral statements or quotes (except those found in a FedEx Sales or FedEx Express Customer Automation agreement) concerning the rates, features of service, and terms and conditions applicable to FedEx Express service will be controlled by the FedEx Service Guide, as modified, amended, changed or supplemented. "

Note: Rate differences are controlled by the service guide.

If the service guide says there should be no residential delivery charge, and they are adding one, that's a problem.

They also only reserve the right to charge the residential surcharge on certain places:

"We reserve the right to assess a Residential Delivery surcharge on any shipment delivered to a home or private residence, including locations where a business is operated from a home, or on any shipment in which the shipper has designated the delivery address as a residence, including shipments where the delivery location has been designated as Residential Delivery in error. "

The last part is what part of their defense will almost certainly be. As this email shows, however, they've apparently deliberately designated a large number of shipment delivery locations as residential delivery, meaning it was not "in error", but intentional.

Ignoring all of this, they are also usually forming binding rate contracts with businesses and governments (IE you agree to ship this many packages a year, we agree to charge you the rates in this service guide with 80% discount). Throw on top of that that deliberately overcharging the government is serious business in the US. It's often criminal, and IIRC, even in the civil side, you can keep a percentage of the money you recover by suing on their behalf.