I'm definitely having the same problem again w/ verizon but on the first gen iPhone.
The thing is, my old service from alltel did the same thing but was worse. AT&T is marginally better so far but seems to be getting worse with time...wtf???
Has anyone tried calling verizon customer support about this?