hey!
I faced the same issue when I uninstalled the windows service by mistake while still it was running. To resolve this type of issue all I did is this :
a. First uninstalled the dll using the installutil.exe and then
b. Install the .exe using the installutil.exe.
c. The again I uninstalled the msi using the control panel.
After all this I was able to successfully install the windows service and made it it up n running.