I am probably missing something here, but if a delete happens asynchronously wouldn't that make the key still be available?
What happens if you check if that key still exists in a different operation as you're deleting it?
Also, how slow is an operation to rename it before you delete it?
Also, how slow is an operation to rename it before you delete it?