Index: apps/app_voicemail.c
===================================================================
--- apps/app_voicemail.c	(revision 37681)
+++ apps/app_voicemail.c	(working copy)
@@ -1540,16 +1540,32 @@
 {
 	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;
+	/* NOTE:  because there is a critical path between finding the
+	 * last index and creating a new one, this routine must be called
+	 * with the path already locked, or else we have a race condition
+	 * between finding the last message index and creating a new one.
+	 */
 
+	/* 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);
 
 	return x - 1;
 }
@@ -2341,13 +2357,8 @@
 	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 {
@@ -2652,12 +2663,8 @@
 					unlink(tmptxtfile);
 					ast_unlock_path(dir);
 				} 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);
@@ -2760,11 +2767,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;
@@ -3978,8 +3983,15 @@
 	detected.
 	*/
 
+	if (vm_lock_path(vms->curdir)) {
+		ast_log(LOG_ERROR, "Could not open mailbox %s:  mailbox is locked\n", vms->curdir);
+		return -1;
+	}
+
 	last_msg = last_message_index(vmu, vms->curdir);
-	if (last_msg < 0)
+	ast_unlock_path(vms->curdir);
+
+	if (last_msg < 0) 
 		return last_msg;
 	else if (vms->lastmsg != last_msg)
 	{