I just had this exact same issue with my iPhone 5. I took it to the Apple Store this morning and they fixed it within 15 minutes. Here's what she did:
1. Plug the phone in and open iTunes
2. When the message comes up asking to restore the phone, do this:
a. Hold down both the top and bottom buttons until the screen goes black
b. Before the apple sign comes back on, let go of the top button and continue holding the bottom button for 8 seconds.
c. After 8 seconds, let go of the bottom button.
d. iTunes prompted me from there.
After it fully restored, I set up my phone as a new iPhone. The Apple Store employee said that I could try to restore my phone from backup using my iTunes when I got home, but that there was a chance that the backup could cause my phone to have the same problem again (constantly saying "searching" and having no cell service). Since my contacts were backed up to my iCloud, I'm just going to play it safe and leave it.
Just to note, the Apple Store employee didn't even hint that the issue wasn't fixable. She seemed to immediately know what the issue was and how to fix it. So for those of you who were told that your phone is now a brick, you may want to try this.