I expect you are correct in that this is most likely a software issue. Since it seems related to how the phone interact with specific network infrastructure, I think it's going to take some time to resolve. In my last call with Apple, the customer support agent was aware of these threads and said other cases had been escalated to engineering, but they weren't aware of an issue on their side at this time. All my contact with Verizon has been there is no issue, you just got unlucky with a bad phone.
If the phone didn't lose service completely I wouldn't mind as much. I can switch it in and out of airplane mode, but when I lost service completely I needed a full restart to get it back. Since I use my GPS a lot when driving this is far too noticeable of a problem.
Every person I've dealt with at both companies has been nice, and likely done as much as they could at this time. I've actually been impressed with the customer service at both places in the agents trying to do what's in their power to assist. If I had Verizon previously or the network service was superior when it was working I probably would have waited it out. However, even when the service was working it wasn't noticeable better and it is a little more expensive for my needs. As such I don't have much incentive to wait it out instead of just switching back.