I had it happen to me this time around on the Radio Upgrade for the VX6900. Went straight to the Sprint Leaked ROM radio. Granted - it has only happened when I did the initial radio flash. I've re-flashed my ROM to various flavors and variety of builds at least a dozen times since with no problems. (So "no," I don't need to call each time) When I upgraded the radio on my VX6800, I didn't have this issue (plus I didn't have two devices when I had my XV6800). If I had known it was an issue, I would have followed my own advice in the next paragraph
Yes, it is the A-Key. There is one way to avoid it. If you have another smart phone (device that matches your current plan) lying around, use your vzw.com option to activate it BEFORE YOU FLASH YOUR RADIO. (You will need the ESN off the back to do this). Do the *22899 on the spare device and verify that your network works. Then flash your radio on and OS ROM's on your new device. Before you dial *22899 to program your device, you go back to vzw.com and activate this device. This is just like picking up a new device,... the online activation will push a new A-Key to your phone.
Hope that helps.
Chris