+1 on FedEx. I'd rather subject my stuff to airline baggage handlers and TSA before I'd let UPS touch it, and that's NOT because I have a high opinion of airline baggage handlers or TSA.

The whole point of the TSA locks is so they can open and re-lock your bag. They don't open every single one, but if yours is chosen, the less of a maze it is to pack, the greater the likelihood that it'll be re-packed properly. Of course that doesn't mean they'll close the latches. We had the same experience with a Pelican case of photographic equipment. Luckily everything was okay, but it was pure luck.

I've been using FedEx for all kinds of stuff for years, and so far I've shipped my bike FedEx three times (in a Thule case) with no problems. If you have someone on the other end you can ship to, FedEx Home Delivery is super inexpensive. Whatever rate you choose, you get a discount if you print your own shipping label, too.