Normally when a project is deleted, the key can be reused. Are you sure that the project has actually been deleted?
If you're not a DSS administrator, you can only see projects that you have access to. In this case, please check with an administrator to verify if the project exists.
It's also possible that there's an existing project that is using the key, but has a different display name. You can run the following code in a Python notebook to list all existing projects and show their keys & names. The notebook must be created by a DSS administrator; otherwise it will only list projects that you have access to.
client = dataiku.api_client()
for project in client.list_projects():
print("Display name:", project["name"])