So I assume it works now for you also as regards your NFS (NAS share)?

But what I don't understand, how it can fail without delete at all (especially with EEXIST error code).
Possibly you use something like temporary folders (just with range of the same names)? So it could be deleted (after work done)?
In case like this I think to resolve such time-issues (and they are rather a time- as a race-condition indirectly) you should possibly add some business logic (e. g. with some time-component in the name of the folder) to avoid deleting of still "active" directory (as already said like described in RFE [4f322b9d21]).
Note, that in this case both creater-workers will return successfully, but folder will be not exist (because deleted) so you'll get a consequential error just later.

Also note on NFS (especially under control of Windows) there are some rude antivirus or other IDS-similar software's (could use quarantine, worker suspending and co), that may cause similar errors there.