My first major complaint with them is that their delivery software system seems really lacking. Somebody sent me a package recently and didn't include my apartment number. FedEx said they couldn't tell where to deliver it, flagged a "delivery exception", left a voicemail for me, and finally delivered the package 3 days after I called them back and gave them the apartment number.
How come their shipping software didn't automatically flag my street address as one that requires an apartment number when the shipping label was being printed by the sender? And once it was in the system, their software should have been able to check a "delivery address cache" and seen that in the past 5 years, dozens of packges have been delivered to me at my street address, and then used that knowledge to fill in the missing information.
I had a similiar experience a few years back when I sent a package to a P.O. box. I used fedex.com's shipping manager to prepare the label (with barcode). FedEx happily accepted the package, only to tell me 5 days later that there was a "delivery exception", that they don't deliver to P.O. boxes, and that there would be a $5 charge for correcting the address. How come their software didn't simply tell me this when I entered "P.O. Box xxx" on their web site?!
Second major complaint: It seems that they almost always have to come out twice to deliver each package, since I am never here when they try the first time. If you happen to check the tracking web site beforehand, you can see the day that delivery is expected, but it never lists a time. Why can't they give a proactive e-mail/phone call with approximate delivery time range (i.e., early/late morning/afternoon/evening)? This would greatly increase their first-time delivery success rate. Further, I have to imagine that their system already routes trucks along specified delivery routes and thus has to have some approximate estimate of the times.
These seem like two obvious areas that could easily be addressed in software. If FedEx can't roll out simple enhancements like this, I can only deduce that there is some fundamental explanation I'm missing or that their backend software infrastructure is a total mess.