Verizon has a history of blocking navigation apps so we'll be forced to use their proprietary navigation system (VZNavigator) and pay the $10/month subscription for it. Can someone confirm that this does not apply to Google Maps Navigation for Mobile on a Verizon Android phone? I'm specifically thinking about the Droid X.
Yes, it works on Droid X on Verizon (although the app might have unrelated issues): http://androidforums.com/1208709-post1.html
I had a Droid 1 for about a year. Google maps works great. Recently switched it out for a Samsung Fascinate. The Fascinate comes with Verizon Navigator pre-loaded. But I downloaded and installed the Google Maps without any issues. I do not pay for the Verizon Navigator application at the additional $10.00 a month. I also have used TitaniumBackup to "freeze" lots of the preloaded programs from Verizon. Have had zero issues with doing that. The Fascinate had an issue with the GPS taking a while to lock on, but it has recently been addressed in a software update. Using Google Maps and Navigation is something that I use daily.
It doesn't apply to Google Maps Navigation AFAIK but you should ask this specific question to your local Verizon dealer.
For instance, I use Google Maps Navigation on my HTC Droid Incredible and a friend uses it on the Motorola Droid, each with Verizon (but again, be sure to ask before you buy the phone).