I've witnessed Jenkins randomly fail to remove a workspace (job configured with "Delete workspace before build starts" selected). This seems to happen randomly and results in the build failing due to old data being present.
I can force this to occur by opening a command prompt in the workspace before starting the build.
I've had a quick glance at the Jenkins code, and it looks like the call workspace.renameTo call in the Wipeout class is failing silently. This in turn seems to be because the implementation of renameTo in FilePath doesn't check the return value of the java.lang.File.renameTo call.
If the workspace cannot be renamed for any reason, the cleanup should either fallback to deleting synchronously (and still potentially fail due to whatever lock prevented the rename) or immediately report an error.