В том то и дело, что на SERVICE_CONTROL_STOP возвращается: у сервиса нет такого control code.
- GetLastError() какой?
ERROR_INVALID_PARAMETER? или другой?
в SERVICE_STATUS что нибудь возвращается?
перед удалением попробуйте выяснить статус сервиса QueryServiceStatus.
полная процедура удаления сервиса описана в MSDN:
Platform SDK: DLLs, Processes, and Threads
Services
Using Services
Stopping a service
внутренняя ссылка MSDN2004 "ms-help://MS.MSDNQTR.2004JAN.1033/dllproc/base/stopping_a_service.htm"
или на странице
http://support.microsoft.com/kb/245230