Vonage complains about VoIP-blocking

Precisely. You not only don't need a Verisign cert for this, you don't
want one. The phone should trust the authorized operator, which bears
no relationship to an identity that Verisign (or whomever) attests to.

The really interesting question, to me, is how to let users provision
their phones to talk to the operator of their choice. The simplest
solution is probably something like a SIM; it would contain the
customer subscription data and the operator's CA certificate.
Switching providers would be as simple as switching SIMs. (Of course,
that assumes that this time we can avoid SIM-locking nonsense....)

    --Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb

Like a SIM card, you want to give the authentication information to
the user in a form the user can't access themselves. Yes, Virginia
the user really is the weakest link. If the user has access to it,
in the real world it seems like lots of other people can get access
to it. Usernames and N (pick any value for N, it doesn't matter)
character static passwords, blech.

So how does the user's choice of service provider securely deliver the
authentication information to the user's choice of device, without knowing
anything about the user or device ahead of time. Physical hardware (i.e.
a SIM card) works, and we know the physics involved with its security.
But its darn expensive, and people don't like waiting for the mail to
deliver it. Most online methods rely on a pseudo-out-of-band
authentication method, which usually turns into a version of static
password.

It should be easy, but it quickly turns into a hard problem to solve.