Some have made light of the fact that a naming agency was hired to come up with the name "Verizon."
An application for the trademark "Verizon" was filed on September 10, 1999 by NEP, Inc. (a Delaware corporation with offices in Washington, D.C.). On the same date, NEP filed for other trademarks covering the same goods and services. Thus it appears that these were names in the running along with "Verizon," but which didn't make the final cut.
Here they are, obtained from the U.S. Trademark Electronic Service System (http://tess.uspto.gov/):