Unable to publish a service with the same name as a deleted service

Description

After deleting a service from ArcGIS Online, publishing a new service with the same name as the deleted service fails with the following error:

Error:   
ERROR 001398: Service name <service_name> already exists. 

Cause

The error occurs when attempting to publish a service with the same partial name of an existing service.

Solution or Workaround

1. In ArcMap, click File > Share As > Service.
2. Select the Save a service definition file option, and click Next.

3. Select the Choose a connection option, and select an existing connection from the drop-down list.
4. Enter a service name, and click Next.

5. Select a location to save the service definition file, and click Continue. The Service Editor dialog box appears.

6. Set the service definition properties, and click Analyze. Warnings and error messages are displayed in the Prepare window.
7. Fix any errors in the Prepare window, and click Stage. For more information on creating and saving a service definition file, refer to Create a service definition in ArcMap.

8. Sign in to ArcGIS Online.
9. Navigate to My Content > Add Item > From my computer to add the service definition file.
10. Select the service definition file, check Publish this file as a layer, and add tags to describe the file.
11. Click Add Item, and the added file appears in My Content.