The service failed to start due to an error. (4351579)

When reinstalling or installing agents or services or when performing a repair or reinstall of the tool (or part of the tool, module) the following error might be shown when attempting to start a service:

The (Name of the service) service failed to start due to the following error: The system cannot find the file specified.

This is an old well known Microsoft issues with services being marked for deletion. In the past it would say "the service has been marked for deletion...", but now in 2008 the wording has been changed. The MS KB article was: http://support.microsoft.com/kb/823942

Often this was also caused when the Service Control Center (services.msc) was opened and connected remotely or locally to the affected machine, and at the same time the service was reinstalled.
 

Reboot the affected computer (where the service is installed) and the old service should disappear. If you don't see the new service then just install it again and it should start working immediately.

Note: when installing QMM Exch agents there is an option to uninstall or install a service without installing or reinstalling the agent, by using the right mouse menu and clicking on the agent (not on Agent Host). Please see the attached screenshot.
But a reboot is a must when you receive a message mentioned above.