If it isn't in the App Store, it isn't yet available. Not surprising since the official launch of the iPhone on Verizon hasn't even happened yet.
Patience is a virtue in this case. And there are always more options with a single up-front fee that might fit your needs better (TomTom, Navigon, Garmin, Magellan). These would break even with VZ Navigator after a mere 4-6 months of ownership.
Cheaper options exist such as MotionX Drive, which is actually a pretty solid app for the price. (99 cents for the app, 20$/year or 3$/month for the live guidance voices and traffic) It even comes with a month of live guidance as part of the initial 99 cent price.
It's worth checking out some of the alternatives because there are quite a few to choose from to fit your needs and budget.