The problem are the access rights of the service. It runs under an account which isnt granted to run exe files with UI.
If a service want to run exes than you need to impersonate for launching:
BOOL b = ::LogonUser( pszUser, NULL, password, LOGON32_LOGON_INTERACTIVE, LOGON32_PROVIDER_DEFAULT, &hToken );
PROCESS_INFORMATION pi = {0};
BOOL b = ::CreateProcessAsUser( hToken, NULL, (LPTSTR) pszCommandLine, NULL, NULL, TRUE, NORMAL_PRIORITY_CLASS, NULL, NULL, NULL, &pi);