[[seoane]]

La respuesta de roman me parece la mas sencilla en tu caso, pero si quieres hacerlo mas complicado aqui te dejo el codigo para hacerlo desde un programa de Delphi.

Código Delphi [-]
var
 scm: SC_HANDLE;
 srv: SC_HANDLE;
 status: SERVICE_STATUS;
 arg: PAnsiChar;
begin
  scm:= OpenSCManager(nil,nil,GENERIC_EXECUTE or GENERIC_READ);
  if scm > 0 then
    begin
      srv:= OpenService(scm, 'NombreDelServicio', GENERIC_EXECUTE or GENERIC_READ);
      if srv > 0 then
        begin
          // Si no esta parado lo paramos
          if QueryServiceStatus(srv,status) then
            if status.dwCurrentState <> SERVICE_STOPPED then
              if ControlService(srv, SERVICE_CONTROL_STOP, status) then
                Sleep(500);  // Le damos un tiempito para que se pare
          arg:= nil;
          // Lo volvemos a iniciar
          StartService(srv,0,arg);
          CloseServiceHandle(srv);
        end;
      CloseServiceHandle(scm);
    end;
end;

No te olvides de agregar "WinSvc" a las uses.