Most of the time, voicemail full messages happen because deleted voicemails are still sitting in the "deleted messages" area still.
Here is how to rectify this issue:
Permanently erase deleted voicemail
Deleting an emailed voicemail puts it in the phone system's trash, but does not remove it permanently. (similar to deleting a traditional email message Where it goes into the Outlook trash) This may cause some phone mailboxes to fill up.
To empty the trash: (note: careful listen to the option numbers. Depending on folder status, numbers may change)
• Dial 516-367-5000
• "enter your ID" (this is your extension)
• enter your 4 digit extension, then #
• "enter your PIN"
• enter your personal PIN, then #
• "you have X saved messages..."
• 3 = Review old messages
(note: the following numbers may change depending on messages in your mailbox: new/saved/deleted)
• 1 = Saved messages
• 2 = Deleted messages
• 1 = Review deleted message (listen individually and retrieve, or permanently delete each one)
• 2 = delete messages (all of them)