I second this that Verizon is full of Bull, we have done this with our Nortel CS1k and it works very well.
You just add a Calling Party Privicy activate code.
It works perfectly, BTN will not go out. It shows up as Private to the called party.
It works well with Verizon, have yet to try this on...