A system for processing voicemail is provided that includes a voicemail database processor establishing one or more of an accounts table, a messages table, a distribution list table, a distribution lists members tables, and a delete request table. In operation a message navigation menu is provided to a user to allow the user to move back and forth a specified number of voicemails, change between urgent and normal priority voicemails, retrieve messages only from a specific mailbox or from outside the system, or initiate an improved deletion operation.