I tried to use the sc.exe delete "Servicename" and it said that the "Service has been marked for deletion". Earlier, I had used installutil /u to uninstall it. Since, both of them did not work, I wasnt sure what else I had to do. Then, I realized that I had the services MMC open. Close it and the service gets deleted.