Я не уверен, у вас все еще есть эта проблема или нет, но все еще даю ответ, чтобы она помогала другим.
Используйте компонент установщика вместе со службой Windows, переопределите метод OnBeforeUninstall и напишите свой собственный код для отмены регистрации службы, например:
{frameworkpath}\InstallUtil.exe /u <serviceinstalledpath>
Это должно удалить ваш сервис