I also run it the same problem and did all of tricks in the book... from taking apart the complete phone to checking all of the connectors under microscope and reseting the network settings too... nothing helped...
However the solution was much simpler in the end...
If you disconnected the battery while you were doing any repairs (as you should!) the date on the iPhone should change to the year 1970 or something like that and the connection with the cell tower is not possible... do not ask me why...
After I changed the date I got full reception right away...
I guess it would work if you reset the phone completely since the iPhone would sync with the iTunes on the computer so it should pick up the date too...
Also the connection to the wireless network could also help however at the time I was not connected to the wireless internet at all so I am not able to verify that...
So before you do anything else and have similar "searching" issue check the date first....