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?