The 3rd party application uninstaller had removed the files for the service and then left the service in this pending deletion state.
After trying to close all applications, identifing PID of service(couldn't) for kill, logging off all other users and logging off and on, rebooting was the only fix that worked for me.