Are you sure? Maybe I'm not understanding something.

I thought the GPS gets its location independent from the cell network, from the satellites in orbit. Then (I assume) all it needs to do on the phone is to overlay that position (hopefully correctly) on the map cached on the phone. . .I think you could still use that for navigation. Thus, you would want the relevant map data stored on your phone.