Uma solução para o problema foi fazer o serviço ser executado automaticamente pelo windows, e não pelo trayIcon que eu tinha para controlar o serviço.
Para isso eu criei o serviço através de alguns registros do windows. Segue abaixo as linhas de comando utilizadas no InnoSetup para escrever nos registros.
;registros adicionados para controle de permissão
Root: HKLM; Subkey: SYSTEM\CurrentControlSet\Services\{#ServiceName}; ValueType:string; ValueName:ObjectName; ValueData: "LocalSystem"; Flags: uninsdeletekey;
Root: HKLM; Subkey: SYSTEM\CurrentControlSet\Services\{#ServiceName}; ValueType:string; ValueName:Description; ValueData: "Servico"; Flags: uninsdeletekey;
Root: HKLM; Subkey: SYSTEM\CurrentControlSet\Services\{#ServiceName}; ValueType:string; ValueName:DisplayName; ValueData: {#MyAppName}; Flags: uninsdeletekey;
Root: HKLM; Subkey: SYSTEM\CurrentControlSet\Services\{#ServiceName}; ValueType:expandsz; ValueName:ImagePath; ValueData: {app}\service.exe; Flags: uninsdeletekey;
Root: HKLM; Subkey: SYSTEM\CurrentControlSet\Services\{#ServiceName}; ValueType:dword; ValueName:ErrorControl; ValueData: 1; Flags: uninsdeletekey;
Root: HKLM; Subkey: SYSTEM\CurrentControlSet\Services\{#ServiceName}; ValueType:dword; ValueName:Start; ValueData: 2; Flags: uninsdeletekey;
Root: HKLM; Subkey: SYSTEM\CurrentControlSet\Services\{#ServiceName}; ValueType:dword; ValueName:Type; ValueData: 16; Flags: uninsdeletekey;
Root: HKLM; Subkey: SYSTEM\CurrentControlSet\Services\{#ServiceName}; ValueType:dword; ValueName:WOW64; ValueData: 1; Flags: uninsdeletekey;
mais informações nos links abaixo:
http://support.microsoft.com/kb/259733/pt-br
http://support.microsoft.com/kb/165748/EN-US
Único problema com essa solução é que o usuário que não for administrador não poderá parar o serviço. Mas isso não é um grande problema para a minha aplicação.