opinions
I think I've posted thoughts on this issue elsewhere, but here it goes again. I don't know much about CDs, but these are opinions on some vinyl shops.
sandoxautomatic.com has a good selection and I've been impressed w/their service.
I recommend hiphopsite.com b/c the guys who run the place are cool and they add value on their site through reviews, etc. They are true hip hop fans and it's people like that that will keep good hip hop alive.
musicfactory.com probably has the quickest service. I got burned a few months by them once b/c some records I bought skipped straight out of the sleeve. I eventually realized that the record quality was the cause and that I should stay away from bootlegs. I have since ordered from them and have been impressed.
Best bang for your buck is musicfactory. Hiphopsite and sandboxautomatic have a great selection and depending on what I'm looking for, I'll spend the extra couple of bucks to support both sites.
Regarding your complaint on the handling of your CDs, hiphopsite has a physical store too so they are theoretically better in taking care of their products (b/c people actually view the products; the products don't just sit in some warehouse). Hope this helps.