My experience with UPS has also been abysmal. Eleven years ago, they delivered a very expensive (for the student I was at the time) piece of audio equipment, but broken: the package had been pierced and crushed. They took it back, admitted they were at fault in a letter, and... that's it. I never saw the package again, nor did they reimburse anything, nor did they answer any more letters, even registered. I asked advice from a lawyer, but she said that they could afford to ignore me, while I couldn't afford to sue them (that's France for you). I wish I'd known about the BBB at the time.
I also had a problem with DHL: I paid their premium for documents to be delivered before a meeting, and they arrived too late, putting me in a very bad position.
USPS and FedEx: never any problem.
EMS: never tried.
My Faves: EMS, Canadapost, Collisimo (all extremely well done)
Never had troubles with: USPS, FedEX and Purolator