Agreed, to actually be sure, the software needs to be at least verified by someone you trust. It would not be wise for that someone to be a telco. However, end-to-end has a specific meaning and Verizon's service isn't it.
As for the keys, you can identify the party through conversation. If you've never met, you would need a trusted introducer in a 3 way call to verify each of you to the other. Then transmit public keys around and read back the key fingerprints. In other words, use the PGP/GPG web of trust rather than a central authority.
From then on, you have the keys stored and so you can skip that part.
I do know very well that the company is not at all immune to government pressure. I never anywhere suggested otherwise. I suggested that claiming a thing that is untrue and legally cannot be true is immoral. A moral company simply wouldn't claim to offer end to end encryption.