I faced the same problem. Scenario:

1. Compile MSI
2. Install program using msi
3. Remove program using the same msi

In Remove mode installer wasn't trying to stop/delete windows service (according to Event Viewer). The final result was that service .exe wasn't deleted and service was in Running state.

As my installer of previous versions wasn't ever been published, I've just changed Component GUID once, then it starts to stop and delete service.

I don't know the original reason of such behavior, but I guess that the reason is manual service deletion using MS util: https://support.microsoft.com/en-us/topic/fix-problems-that-block-programs-from-being-installed-or-removed-cca7d1b6-65a9-3d98-426b-e9f927e1eb4d