iPhone 3GS
iOS 4.0
Baseband 05.11.07
Jailbroken with PwnageTool 4.01
Unlocked with ultrasn0w 0.93
Purchased with contract from AT&T, now being used with Vodafone in Italy

For about a week now, my phone will mysteriously and at random drop into "Searching..." for an extended period of time until finally changing to "No Service". This does not depend on location, as it happens anywhere I go, nor time, as it happens at all hours. It does seem, strangely, to be time-based, that is, if I let it sit for 20-30 minutes the signal will eventually come back. Oddly, if I remove the SIM card at this time, it will sometimes even remain at "Searching..." or "No Service", without changing to "No SIM" (though not always). This leads me to believe it is hardware-related, also because I have been using the phone unlocked for about a year now and installed iOS 4 about a month ago, but only recently started seeing this issue. Scouring the internet, I have found and attempted all of the following remedies, all without success:

Toggle Airplane Mode
Disable 3G
Remove SIM card and re-seat
Turn on Airplane Mode, remove SIM card, replace SIM card
Reboot phone (Soft and Hard)
Reset Network Settings
Reset All Settings
Erase All Content and Settings
Restore OS from backup (this I tried many times)
Restore OS as a new phone
Downgrade to iOS 3.1.3
Install BossPrefs before unlock (3.1.3)
Tape SIM card to SIM tray
Holding phone in every way imaginable
etc...

Oh yes, I've tried multiple SIM cards (AT&T as well as other carriers) in the phone with the same result. And I've placed my SIM into another iPhone and it worked perfectly.

Please help, I don't know what else to try!

Reload the baseband to a higher version (3.1.3 or 4.0 - ultrasn0w supports both) and test again.
Otherwise - it is likely hardware.

Originally Posted by Olethros

Reload the baseband to a higher version (3.1.3 or 4.0 - ultrasn0w supports both) and test again.
Otherwise - it is likely hardware.

Yep. Friend of mine had this exact behavior on his iPhone 4, turned out to be a bad SIM slot. If the baseband upgrade doesn't work, you may need to have a hardware swap done.

Thank you both. It does indeed seem to be hardware-related. I discovered this after, in an act of sheer desperation and frustration, I slammed the phone down on the table and, lo and behold... it started working!

I realize this is not a recommended fix and as soon as I get back stateside I will do a hardware swap, but in the mean time if it ever acts up, all I have to do is give it a quick slap and I'm good to go!