I've noticed the same with my 3GS; and this is happening much more often than with my v1 iPhone and my 3G. I've not found a fix, yet....😱😱😱
UPDATE: It searches while I'm on WiFi more than anything else. Most notable, is the fact that the cell phone/data bars are 0-1 at the most and many times "No Service" switching in and out, and eventually "Searching..."