Why concurrent runs of shred cause "No such file or directory" errors ?

Issue

• Several instances of the same script are run daily at the same time.
• The script uses shred -u to delete its temporary files before exiting.
• Once in a while, one of those instances output the following error :

shred: /tmp/debug_mktemp.RzwT6UQB: failed to remove: No such file or directory

• Running an strace on the command, it appears to be a race condition, since shred does several renames to a fixed name before actually deleting the file. Sometimes, between it checking if the file already exists and its renaming, another instance of shred obviously creates it or rename it.
• It has been very easy to reproduce.