Hi,
Note that the problem is the alias (the text used in the URL to reach the page of the category), not the name. So you need to check whether another category has the same alias or not, not the name.
There is no check on the name, so even if you have categories with the same name, the system won't display any error and it will work just fine.
However, since the alias is added in the URL of the category, and the system needs to find the category based on the alias in the URL in order to display the correct page, the alias has to be unique so that there is no ambiguity.
Also, once a category is deleted, it is completely gone. So the system shouldn't bother you about the alias if you try to create another one with the same alias.