I don't think this has anything to do with parallel jobs execution ... except perhaps that it is easier to expose the race condition?
We see the same failures to update permalinks – both lastSuccessfulBuild and lastFailedBuild – on a small installation without parallel jobs (one node, with #executors set to 1) and with low execution rates. Also the server is Windows Server 2012 R2 Standard, so not a linux-only issue. Jenkins ver. 1.642.2.
Another difference is that instead of NoSuchFile, we see DirectoryNotEmptyException:
Mar 05, 2016 4:06:09 AM jenkins.model.PeepholePermalink updateCache
WARNING: Failed to update hudson.model.FreeStyleProject@320509[40018_mmiDotNetMath_main] lastSuccessfulBuild permalink for 40018_mmiDotNetMath_main #767
java.nio.file.DirectoryNotEmptyException: C:\Jenkins\jobs\40018_mmiDotNetMath_main\builds\lastSuccessfulBuild
at sun.nio.fs.WindowsFileSystemProvider.implDelete(Unknown Source)
at sun.nio.fs.AbstractFileSystemProvider.delete(Unknown Source)
at java.nio.file.Files.delete(Unknown Source)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at hudson.Util.deleteFile(Util.java:255)
at hudson.util.AtomicFileWriter.commit(AtomicFileWriter.java:113)
at jenkins.model.PeepholePermalink.writeSymlink(PeepholePermalink.java:200)
at jenkins.model.PeepholePermalink.updateCache(PeepholePermalink.java:150)
at jenkins.model.PeepholePermalink$RunListenerImpl.onCompleted(PeepholePermalink.java:237)
at hudson.model.listeners.RunListener.fireCompleted(RunListener.java:201)
at hudson.model.Run.execute(Run.java:1783)
at hudson.model.FreeStyleBuild.run(FreeStyleBuild.java:43)
at hudson.model.ResourceController.execute(ResourceController.java:98)
at hudson.model.Executor.run(Executor.java:410)
Quite similar issue has been fixed for Windows in 1.509.3