I have shipped hundreds of packages with FedEx and never had any problem before. In fact, watches that I buy in Switzerland come only with fedex. Next day delivery from Basel to Charlottesville is guaranteed unless the package gets stuck in customs. But theft? never ever.
The lesson learned: Never drop expensive item in fedEx box. Instead give it to Fedex lady and make sure she scanned it in your presense, or at least obtain some proof that the package got accepted by FedEx. The boxes can be easily opened. I asked the driver who empties that very box daily to show my the lock and inside of the box. Believe me, every thief can open it.

On the other hand, I had problems with USPS as an ebay seller. Three times they lost packages and it took me forever to reach someone on their 1-800 number. Last package that got lost/stolen was shipped to the UK in April of this year with Express mail. It never got delivered and I filed the claim in March. I did all the paperwork timely but still can't get refund.