How is it possible to get ERROR_KEY_DELETED when I'm creating a key? - The Old New Thing
devblogs.microsoft.com
The key that got deleted is not the one you are trying to create.