After 4 weeks of having the phone turned off I finally was able to update it and it is finally working!
I had exactly the same issue of "Searching", then reset everything from factory, then I was not able to use it cause it got stucked in the Hello white screen. Tried also the software update with iTunes but it showed error message, something about servers not being available. I tried that with 2 different macs (both with latest itunes version) and the same issue... But until this week I updated to OSX EL CAPITAN and updated the iphone through iTunes without an issue !!!. The installation was flawless and the celluar signal came back. My iphone 5s is working in great condition now. I was so close to sell the phone as scrap. Please, before doing anything radical try updating to El Capitan or at least to use iTunes from a mac with El Capitan to update the firmware of the iphone. I hope this helps somebody out there.