So it was the SIM card afterall... *facepalm*
Couldn't find a corporate VZW store, so I had to go to a retailer, and like you said, they charged me. $10, so it wasn't too bad.
But I switched on Wednesday, and I have dropped down to 3G exactly one time, when I was in a particularly bad area. Flashed 4.2.1 clean and 4.3.0 dirty, and have been running fine ever since. Don't know why I waited so long to address the SIM card. I really wish there was some kind of useful diagnostic tool that could identify SIM cards that have gone bad.
Although this thread is Note centric, the second post describes the problem I was having perfectly (understanding after the fact...): http://forums.androidcentral.com/ver...er-go-bad.html
Thanks again for everyone's help. I'm going to modify the original post.