Call voicemail box and listen and delete each message.
1. Dial “1” (press and hold to connect to mailbox.
2. Listen to messages.
3. Delete each one by pressing (dialing) “7”
The iPhone is not controlling Verizon’s mailbox very well. The amount of iPhone storage you have does not affect whether a Verizon mailbox is “full”...