The gps status trick works. It doesn't have to stay on the whole time you're navigating, it just helps you get a recent fix. If you then close it and open maps, you get an immediate fix.
What gps status does to get you that fix is, it refreshes the agps (assisted gps) data. This gives the gps a good idea of where it is in general, which helps it lock satellites. On this phone, that agps data seems crucial to getting a lock at all. Shouldn't be that way but it is. All the other gps fixes you see posted - from phone reboots to dialer resets etc - all cause the agps data to be refreshed, and that's what it takes.
So set a shortcut to gps status on a homescreen. Set the gps status prefs to update agps data on every start. Then, if you haven't used gps in more than, say, an hour or 2, tap that gps status shortcut, get a quick lock, close it, open maps. I think this is why telenav works, it probably refreshes agps on every start. It would be cool if someone could hack googles maps and nav to do this.
Oh - once you have a lock and are navigating, you won't lose it if you drive in and out of cell coverage. Once you have a lock, gps is independent of cell/data coverage. You just need it to GET the lock, to refresh that agps data.
So yeah, not how a gps should work, but once you understand the problem, the workaround isn't TOO bad I guess.