Index: sys/fs/nfsclient/nfs_clvnops.c
===================================================================
--- sys/fs/nfsclient/nfs_clvnops.c
+++ sys/fs/nfsclient/nfs_clvnops.c
@@ -1040,8 +1040,15 @@
 	nmp = VFSTONFS(mp);
 	np = VTONFS(dvp);
 
-	/* For NFSv4, wait until any remove is done. */
+	/*
+	 * Return ENOENT if the directory we're searching in has been deleted;
+	 * for NFSv4, wait until any remove is done.
+	 */
 	mtx_lock(&np->n_mtx);
+	if (np->n_flag & NREMOVED) {
+		mtx_unlock(&np->n_mtx);
+		return (ENOENT);
+	}
 	while (NFSHASNFSV4(nmp) && (np->n_flag & NREMOVEINPROG)) {
 		np->n_flag |= NREMOVEWANT;
 		(void) msleep((caddr_t)np, &np->n_mtx, PZERO, "nfslkup", 0);
@@ -2149,6 +2156,7 @@
 	struct vnode *vp = ap->a_vp;
 	struct vnode *dvp = ap->a_dvp;
 	struct componentname *cnp = ap->a_cnp;
+	struct nfsnode *np;
 	struct nfsnode *dnp;
 	struct nfsvattr dnfsva;
 	int error, dattrflag;
@@ -2157,6 +2165,12 @@
 		return (EINVAL);
 	error = nfsrpc_rmdir(dvp, cnp->cn_nameptr, cnp->cn_namelen,
 	    cnp->cn_cred, cnp->cn_thread, &dnfsva, &dattrflag, NULL);
+	if (error == 0) {
+		np = VTONFS(vp);
+		mtx_lock(&np->n_mtx);
+		np->n_flag |= NREMOVED;
+		mtx_unlock(&np->n_mtx);
+	}
 	dnp = VTONFS(dvp);
 	mtx_lock(&dnp->n_mtx);
 	dnp->n_flag |= NMODIFIED;
Index: sys/fs/nfsclient/nfsnode.h
===================================================================
--- sys/fs/nfsclient/nfsnode.h
+++ sys/fs/nfsclient/nfsnode.h
@@ -158,6 +158,7 @@
 #define	NNOLAYOUT	0x00020000  /* Can't get a layout for this file */
 #define	NWRITEOPENED	0x00040000  /* Has been opened for writing */
 #define	NHASBEENLOCKED	0x00080000  /* Has been file locked. */
+#define	NREMOVED	0x00100000  /* Directory has been removed by us */
 
 /*
  * Convert between nfsnode pointers and vnode pointers