This is a simple symptom-cause-solution blog entry only. I hope these blogs will help fellow administrators.
After removing a windows service, when trying to recreate it, the following error may be displayed:
DeleteService failed - The specified service has been marked for deletion. (0x430)
The service is still in-use (at least to some degree).
Close any Microsoft Management Console (MMC) sessions, kill any processes, etc. Note the service can be accessed remotely, so also consider that remote users may be viewing the service.