Creating folder - Duplicate name entry, name already exists error

Deleted existing Net Folder and/or server, recreated Folder and/or server sometimes results in error that folder already exists.
Deleted folder for admin account, recreated folder and error shows up saying that the folder already exists.

Workaround:

1. Add the original Net Folder Server back in, if applicable.
   
2. Do NOT add the Net Folders for the above Net Folder Server (the folders are already there, just invisible)
3. Re-index the Net Folders from Site Administration > Search Index
4. When the re-index is complete (it may take a while given the number of Net Folders), check if the Net Folders are now back
5. If the folders are back, delete the folders, if desired, one at a time (each delete will take time given the amount), otherwise leave them be and use the folders.
   

Deleting Net Folders is sometimes causing folders to be orphaned in the system, so recreating the folders is resulting attempts to create duplicates since the system still believes the folders are present.