First of all my definitions, since they might not meet yours. I've found that generally my experience has run like this from worst to best. Everything is with it pointed south.

Worst case - Cold, Moved, Running lock - CMR - sometimes it doesn't lock.
Attempting to establish a lock,
after a few weeks off (cold)
after moving over 500 miles (moved)
at highway speed (running).

CMS (still) - not moving - 5 to 20 minutes

W (warm, having been fired up in the last couple of days)MR - 5 to 20 minutes

WMS 5 to 10 minutes

WC(close, not having moved far) R - less then 5 minutes

WCS sometimes less than 30 seconds

Two weeks ago I flew from Alexandria VA to Alexandria LA.
Based on past experience I expected a CMS of 15 to 20 minutes. It locked in less than 4.
Subsequent WMS were under a minute and WMR's about a minute.

I sure hope that Diablo warms the GPS up!.

/edit - original system