I sincerely hope that FedEx fails. I once bought the book "FreeBSD Kernel Internals" from informit. They sent it through FedEx. I payed the shipping costs in the informit site, as standard procedure. The book passed through customs fine, then FedEx hold it and told me they would not deliver the book unless i paid them 50EUR. This is their current and common practice here in Portugal. Fsck them.
If it makes you feel any better UPS in France does that to me all the time. It isn't the carriers -- it's the protectionist tax schemes of the EU. I once had a replacement wheel for a kid's stroller sent to me in France from the US. The wheel cost $20, and I had to pay $35 in import duties -- despite that part being unavailable anywhere outside of the US. Blame the government, not FedEx.
That is not the way business should be done. There should be a social responsibility part in every company. Extorting money goes against that.