Make sure to give the VVM enough time to actually delete the voicemail before closing the program. It is a data tranmission taking place after all and the VVM program is excruciatingly sluggish to begin with (mainly speaking of launching). The only thing I can think of is it's trying to complete your initial commands of deleting the voicemail. Next time you delete a voicemail via VVM try waiting 30 seconds before closing the program and see if that helps.
I honestly don't know if that will work or not but it's worth a try I suppose