My wife and I both have verizon we both connect to our cars via BT, we do not have blackberries. I am aware that certain BT profiles are disabled by Verizon (yes, this is a bad idea) but I have never heard of BT being disabled. I know that BT push is one of the disabled profiles as well as some others.
On Howard forums you could find all the informatin (and more) you would need about Verizon and the particular phone andissue ytou are having.
I am not saying what you said is not true, just that I have never experienced this.