With both Microsoft and Google Maps, the map cache on your PDA is minimal meaning that if you don't have a cell tower to triangulate from, you probable don't have data on the phone either.
Multilateration systems require three or more towers, trilateration three, and Time Of Arrival systems require two.
But getting data to Google Maps only requires one tower. If the phone knows where it is via GPS, GMM is useful almost anywhere. I've used it across the Sonoran desert (I-10 PHX-LAX) without difficulty. (I know, I know. Like I'm going to get lost on I-10.)