I might suggest you return back to where we began and consider conducting some of those other suggested steps (WIPE, OS Reload, etc.).
As for BES...something is quite odd there, since the message you received is almost certainly generated by some attempted communication between your device and some BES server somewhere.
You have some very strange things going on, so I definitely would recommend doing a WIPE, then seeing if that helps, and if not proceeding to an OS reload, and even more drastic means. Of course, if your suspicion that all of this is somehow caused by the VZW network is true, then all of your device-level efforts will of course be in vain. But I'm not sure what your alternatives are, especially given what you report as to VZWs willingness to help.
Occam's Razor nearly always applies when troubleshooting technology issues!
New to the Community? Click here and also here for helpful guidance. Also please click here for additional helpful information to guide you as you proceed. I always recommend that you treat your BlackBerry like any other computing device, including using a regular backup schedule...click here for an article with instructions. If anyone has been helpful to you, please show your appreciation by clicking the button. Need a reference to BB10 OS/SR versions? Click here. Need a specific BB10 AutoLoader? Send me a private message.