Index: apps/app_voicemail.c
===================================================================
--- apps/app_voicemail.c	(revision 272124)
+++ apps/app_voicemail.c	(working copy)
@@ -7398,26 +7398,31 @@
 	nummsg = x - 1;
 	for (x = vms->curmsg + 1; x <= nummsg; x++) {
 		make_file(vms->fn, sizeof(vms->fn), vms->curdir, x);
-		if (EXISTS(vms->curdir, x, vms->fn, NULL))
+		if (EXISTS(vms->curdir, x, vms->fn, NULL)) {
 			DELETE(vms->curdir, x, vms->fn, vmu);
+		}
 	}
 	ast_unlock_path(vms->curdir);
-#else
+#else /* defined(IMAP_STORAGE) */
 	if (vms->deleted) {
-		for (x=0;x < vmu->maxmsg;x++) { 
-			if (vms->deleted[x]) { 
-				ast_debug(3,"IMAP delete of %d\n",x);
+		/* Since we now expunge after each delete, deleting in reverse order
+		 * ensures that no reordering occurs between each step. */
+		for (x = vmu->maxmsg - 1; x >= 0; x--) {
+			if (vms->deleted[x]) {
+				ast_debug(3, "IMAP delete of %d\n", x);
 				DELETE(vms->curdir, x, vms->fn, vmu);
 			}
 		}
 	}
-#endif
+#endif /* !defined(IMAP_STORAGE) */
 
 done:
-	if (vms->deleted)
-		memset(vms->deleted, 0, vmu->maxmsg * sizeof(int)); 
-	if (vms->heard)
-		memset(vms->heard, 0, vmu->maxmsg * sizeof(int)); 
+	if (vms->deleted) {
+		memset(vms->deleted, 0, vmu->maxmsg * sizeof(int));
+	}
+	if (vms->heard) {
+		memset(vms->heard, 0, vmu->maxmsg * sizeof(int));
+	}
 
 	return 0;
 }