Index: apps/app_voicemail.c
===================================================================
--- apps/app_voicemail.c	(revision 37143)
+++ apps/app_voicemail.c	(working copy)
@@ -1540,13 +1540,27 @@
 {
 	int x;
 	char fn[256];
+	unsigned char map[MAXMSGLIMIT] = "";
+	DIR *msgdir;
+	struct dirent *msgdirent;
+	int msgdirint;
 
 	if (vm_lock_path(dir))
 		return ERROR_LOCK_PATH;
 
+	/* Reading the entire directory into a file map scales better than
+	 * doing a stat repeatedly on a predicted sequence.  I suspect this
+	 * is partially due to stat(2) internally doing a readdir(2) itself to
+	 * find each file. */
+	msgdir = opendir(dir);
+	while ((msgdirent = readdir(msgdir))) {
+		if (sscanf(msgdirent->d_name, "msg%d", &msgdirint) == 1 && msgdirint < MAXMSGLIMIT)
+			map[msgdirint] = 1;
+	}
+	closedir(msgdir);
+
 	for (x = 0; x < vmu->maxmsg; x++) {
-		make_file(fn, sizeof(fn), dir, x);
-		if (ast_fileexists(fn, NULL, NULL) < 1)
+		if (map[x] == 0)
 			break;
 	}
 	ast_unlock_path(dir);
@@ -2341,13 +2355,7 @@
 	if (vm_lock_path(todir))
 		return ERROR_LOCK_PATH;
 
-	recipmsgnum = 0;
-	do {
-		make_file(topath, sizeof(topath), todir, recipmsgnum);
-		if (!EXISTS(todir, recipmsgnum, topath, chan->language))
-			break;
-		recipmsgnum++;
-	} while (recipmsgnum < recip->maxmsg);
+	recipmsgnum = last_message_index(recip, todir) + 1;
 	if (recipmsgnum < recip->maxmsg) {
 		COPY(fromdir, msgnum, todir, recipmsgnum, recip->mailbox, recip->context, frompath, topath);
 	} else {
@@ -2651,12 +2659,8 @@
 						ast_log(LOG_DEBUG, "The recorded media file is gone, so we should remove the .txt file too!\n");
 					unlink(tmptxtfile);	
 				} else {
-					for (;;) {
-						make_file(fn, sizeof(fn), dir, msgnum);
-						if (!EXISTS(dir, msgnum, fn, NULL))
-							break;
-						msgnum++;
-					}
+					msgnum = last_message_index(vmu, dir) + 1;
+					make_file(fn, sizeof(fn), dir, msgnum);
 
 					/* assign a variable with the name of the voicemail file */	  
 					pbx_builtin_setvar_helper(chan, "VM_MESSAGEFILE", fn);
@@ -2759,11 +2763,9 @@
 	if (vm_lock_path(ddir))
 		return ERROR_LOCK_PATH;
 
-	for (x = 0; x < vmu->maxmsg; x++) {
-		make_file(dfn, sizeof(dfn), ddir, x);
-		if (!EXISTS(ddir, x, dfn, NULL))
-			break;
-	}
+	x = last_message_index(vmu, ddir) + 1;
+	make_file(dfn, sizeof(dfn), ddir, x);
+
 	if (x >= vmu->maxmsg) {
 		ast_unlock_path(ddir);
 		return -1;