I have had similar issues in the past where cached services were not removed completely.
In addition to deleting the service in ArcCatalog or Manager, the cache and input folders may also need to be deleted from the arcgisserver/arcgiscache and arcgisserver/arcgisinput folders respectfully.
Depending on where you installed your instance of ArcGIS Server, the arcgisserver folder will be on whatever drive you specified during installation.
The cache and input will have the following syntax: <foldername>_<servicename>.
Once deleted, republish the service. It should recreate the input folder, and if you cache the service again, a new cache folder will be created.
Hope this helps!
Chris B.