I used a third party app to test my GPS signal. With the Verizon iPhone 4 under my windshield with full view of the sky and flat farmland around as far as the eye can see, it lost signal for 15 seconds with all the information on the app reading "Invalid". Then it would lock again. Then a few minutes later, "Invalid". I think the Verizon iPhone is sending GPS apps bad data every now and then. It's just that some GPS apps can hide the iPhone's crazy ramblings long enough for it to come back to its senses.
Navigon is flawless on the AT&T phone and schizophrenic on a Verizon phone. You'll be stationary and Navigon will show you in the correct position, the facing sideways, then 50 feet to the left, then in the correct position again...
I've done a lot of testing on my Verizon iPhone and AT&T iPhone and have come to the conclusion that it is either a firmware, OS, or hardware problem. The drop of signal happens with any GPS app I use, excluding the Google Maps app. While the same GPS apps work flawlessly on an AT&T iPhone 4.