Do what i did. I downloaded the Message+ app. It's the Verizon messaging app. After you download it and set it up, delete all the messages in that app. It deletes a ton of old messages on the Verizon servers. You can then either delete or keep that app on the phone. Reboot the phone. I haven't had a missed message in 2 weeks since I did that. You are basically starting with a fresh slate on the Verizon servers.Verizon
FWIW, I kept the app on my phone, but turned off all notifications for that app.