How to remove ArcGIS 10.0 Server Service and create a new one with the same name?

I want to delete an ArcGIS 10.0 AGS Service and create a new one with the same name. AGS tells me that this is not possible because the Service already exists. I have however deleted the service and the msd and the AGS Cache, but it is still not allowed. What do I need to do so that I can do this?