I swear the next time I see this message on the top left corner of my iPhone 4 I'm going to blow. Seriously. The 3GS with AT&T was not great shakes in terms of getting good coverage but I knew where the dead spots were around the places I go and could count on reduced coverage in those areas. With the iPhone 4 it's like a free-for-all. I can have the phone sitting right in front of me and the signal strength varies from five bars of 3G to two bars of Edge to the aforementioned "Searching...." I've never seen an iPhone "Searching..." as much as this one.