You can reproduce the error by running:
Directory.CreateDirectory(@"C:\Temp\a\b\c\");
Process.Start(@"C:\Temp\a\b\c\");
Thread.Sleep(1000);
Directory.Delete(@"C:\Temp\a\b\c");
Directory.Delete(@"C:\Temp\a\b");
Directory.Delete(@"C:\Temp\a");
When trying to delete directory 'b', it throws the IOException "The directory is not empty". That's stupid since we just deleted the directory 'c'.
From my understanding, the explanation is that directory 'c' is stamped as deleted. But the delete is not yet commited in the system. The system has reply the job is done, while in fact, it is still processing. The system probably wait the file explorer has focus on the parent directory to commit the delete.
If you look on the source code of the Delete function (http://referencesource.microsoft.com/#mscorlib/system/io/directory.cs) you will see it uses the native Win32Native.RemoveDirectory function. This do-not-wait behavior is noted here :
The RemoveDirectory function marks a directory for deletion on close. Therefore, the directory is not removed until the last handle to the directory is closed.
(http://msdn.microsoft.com/en-us/library/windows/desktop/aa365488(v=vs.85).aspx)
Sleep and retry is the solution. Cf the ryascl's solution.