I can confirm one thing here... This isn't a Verizon issue. This is very much an Apple issue. Most don't realize that almost everything you do goes through Apple's servers to verify authenticity, and when their servers are on the fritz, there's little you will b able to do on your phone. I've spent hours trying to troubleshoot issues that Apple created.

I had the I message issue when I went from iPhone back to Android. I went almost six months not getting texts from iPhone users. I agree with vzwinagent's assessment that you need to log into iMessage on the old device and turn it off. You MUST be connected into WiFi. If you don't have this device any more, or its no longer on your Apple ID, you may just have to wait it out.

As for why the AT&T phone didn't have this problem before, that was probably before Apple had three US carriers selling 10 million iPhones a month.