Pues todo lo que haz hecho está bien. Ahora bien, ¿puedes indicarme por favor qué error te sale cuando mandas a desintalar el Windows Service desde "Add/Remove Programs"?
Por otro lado, puedes hacer uso de la herramienta para instalación/desinstalación de servicios Windows, llamada "InstallUtil", que viene con el SDK del .NET Framework. Para utilizarla, solo abre un command prompt de Visual Studio 2005, dirígete al directorio donde instalaste el servicio y ejecuta lo siguiente:
installutil /u tuServicio.exe
Eso desinstalará por completo el servicio de tu PC. Luego que hagas esto, vuelve a tratar de instalar y desinstalar el servicio desde "Add/Remove Programs". Es posible que el error ya se haya corregido.
Saludos,
Julio