You need to diagnose the problem better before you can solve it, which probably means finding a way to reproduce it while program is executing under the debugger. Some suggestions.
You need to diagnose the problem better before you can solve it, which probably means finding a way to reproduce it while program is executing under the debugger. Some suggestions: Since your service is EXE (and not DLL that runs under svchost. Exe, which is a generic host process name for services that run from DLLs), you should be able to use "Attach to Process" option in Visual Studio to attach the debugger to it.
You might need to start the Visual Studio as administrator and/or change the user under which the service executes to be able to do that. Also, if the service crashes soon after starting, you might need to call MessageBox with MB_SERVICE_NOTIFICATION to pause execution long enough so you can attach the debugger. However, if the service crashes during startup before it even reaches the MessageBox, you need to build it as console application.
Now you can actually start it under the debugger and see what is going on.
Can you please try installing redistributable package on client machine to run your application.