Update 27 Nov 2012: This problem has now been resolved with version 3.7 (Build 435)
More information
Since the Search Manager was a 32-bit WOW process on 64-bit Windows when it created a service on a remote 64-bit machine the service was marked as a 32-bit service. That was the the core problem since the service was actually a 64-bit service. The event viewer reported 'The system cannot find the file specified' because the WOW File System Redirector was looking in the wrong System32 folder for the service.
Now the Search Manager app runs as a native 64-bit process on 64-bit Windows the service is correctly installed.