I just had this issue and read this thread, and several others, before taking my phone to someone else for repairs. I cracked my screen on my black 4g and had it replaced with a white front and back. After it was replaced my signal read searching and 'no service' unless i was driving or in an apple store apparently. I normally get great service at home and at work but now i was getting a 'no service' message. I tried all the resets, restoring from a backup, and anything else you can think off for a software solution. Apple gave me a new sim card and told me they couldnt touch my phone or send it in and give me a replacement for $150 unless my phone was back to its original state. My phone was also now missing the silver netted piece that goes over the speaker on the face of the phone (the one you listen out of when your talking on the phone). My home button is also still black, so its obvious my iPhone has been repaired. I found another person (the person that fixed the screen and the guy that fixed the signal were both found on craigslist) that repairs iPhnes and I explained the different possible issues and when we popped the back off the blue wire was not fastened or 'clicked' in place. Once he got the blue wire connected everything was back to normal on my phone. He even replaced the netted piece missing from my speaker. Now my phone is factory new, and white with a black button thought my bumpers still have wear).
Bottomline, i think this 'no service' message is an isolated issue. I believe it shows for many reasons, and even phones that apple repair and refurbish experience damage in the process that apparently isnt detected before sending these phone out to customers. Regardless, if you have an iPhone on a wireless contract and your experiencing this problem my advice is to take the phone to apple and have them replace it if you still have it under a warranty (i got my black 4g iPhone with the firsy batch in 2010 so my phone is no longer under warranty, which is why they said i could pay $150 for a replacement IF my iPhone was in its oringal form). You can do that OR find someone thats a knowledgable iPhone repair-man that can take your phone apart and examine each of these possibilities. He charged me $20 to connect that blue wire and replace the missing piece. There is no one answer for this general problem. Have your phone looked at or buy a new one. GOOD LUCK! -message sent from my new screen, white front and back, black home button, worn down bumper-having iPhone-
Southern Cali resident