First off there is some misinformation about how GPS works here. Fadelight gave possibly the worst description ever on how it works. Heres a brief summary on what actually happens. GPS satellites broadcast two signals, one gives a catalog of the ephemeris data for the satellites... in other words, it tells your GPS unit exactly where the GPS satellites are. The other signal is nothing more than a time stamp. When you have recvd time stamps from 4 or more satellites you can figure out exactly what the "real" time is. Once you know the very precise atomic time you can then use additional time stamp transmissions from the satellites, and the time you recvd them to determine your distance from that particular satellite. If you can figure out the distance from 3 satellites you then know where you are (This is why the catalog of satellite orbits is needed... this catalog is preloaded on some devices so they can quickly acquire, otherwise it takes about 2 minutes of uninterrupted signal to get the full catalog). Any more than 3 satellites will reduce error (from about 100 m down to a few meters) and the geometry of available satellites (see GDOP) also determines error.
Ok, hope that wasn't too long winded but it should dispel some of the theories here.
Now, my problem is very similar to many others, it worked for awhile flawlessly with very little time to acquire a signal. However i started getting the same searching for gps. At first a cold restart would fix it, and now even that doesn't work. I'm not an Alltel customer and I'm not in FL (although it did work down there yesterday when I was there).
In my opinion this could be a few things... hardware issue such as a loose antenna wire, although this is unlikely since i would imagine it uses the same antenna for GPS, phone and wifi, and I haven't had any issues with the other two.
Given the fact that the cold restart did fix it a few times... it is most likely a firmware/software problem which can be fixed with an update. But Motorola/VZ needs to get on this ASAP or I'm guessing a lot of Droids will be returned before the 30 days runs up.