In preparation for the dreaded eternal "Searching for GPS..." event, install the "GPS Status" application from Android Market. (Gratuitous plug: I found it so useful and well done that I made a contribution.) It provides a bunch of useful non-navigation GPS and other function including:
- GPS receiver control functions (needed for this purpose)
- a graph of GPS satellites in view and their respective signal strengths.
- complete GPS location, altitude and speed
- magnetic and GPS (if currently locked-in) compass information
- the orientation of the phone similar to a spirit level
- battery power level
- ambient light level
When your GPS fails to lock-in and gives you the:
- Open the GPS Status application.
- Press the Menu button, Tools and "Manage A-GPS state".
- Select the "Reset" button to clear the current GPS data.
- Once again, press the Menu button, Tools and "Manage A-GPS state".
- Select the "Download" button to get a new copy of the GPS assistance data (apparently provides clues to the GPS about where you are located.)
At this point my GPS has, almost immediately, locked in and provided a route routing. I do not know if both "Reset" and "Download" are necessary but it is very quick to do both.
It seems to me that all of the suggested fixes above have the common effect of forcing a complete reset of the GPS system.