I had the exact same problem ... until yesterday when I ran across a post recommending to change my radio rom. I flashed the following radio, and it worked immediately.
1.03.09V
That's the Verizon rom found in the '
radio rom' sticky. You can find a FAQ about upgrading your radio rom in that thread.
Hope that fixes you up as it did for me. I was pulling my hair out for days and through many rom flashes until I figured that out. Good luck.