Other people have commented on the payment issue - I'm glad you're looking into bitcoin.
I'd be worried about delivery, too. I know you say you destroy customer information immediately, but if I'm truly paranoid I'm not going to trust that statement - I'd rather pay someone on craigslist to buy a bunch of prepaid phones for me.
I'm just brainstorming, but would it be possible to set up some sort of physical tor/mixmaster style forwarding that would keep the final destination of the phone from ever being known to you? I'm not entirely sure how that would work, and it would probably be open to abuse, but it's an interesting thought.
Also, could you consider posting something like rsync.net's warrant canary?
http://www.rsync.net/resources/notices/canary.txt
It's not perfect, but it is a nice touch.