tl; dr
Meu SDDL estava incompleto. Eu precisava adicionar SW (EnumDeps) às permissões LCRPWP já adicionadas no SDDL.
Versão longa
Aqui está a versão (higienizada) do meu SDDL (quebrado):
D:(A;;CCLCSWRPWPDTLOCRRC;;;SY)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;CCLCSWLOCRRC;;;IU)(A;;CCLCSWLOCRRC;;;SU)(A;;LCRPWP;;;S-1-1-11-1111111111-1111111111-1111111111-1111)
O problema está nas permissões da última cláusula:
(A;;LCRPWP;;;S-1-1-11-1111111111-1111111111-1111111111-1111)
O SID S-1-1-11-1111111111-1111111111-1111111111-1111 está correto para o grupo DOMAIN \ Tomcat Restarters que DOMAIN \ tomcat .restarter é um membro de. Isso está certo. As permissões concedidas ( LCRPWP ) são insuficientes para Restart-Service .
Para que o cmdlet Restart-Service funcione, ele precisa do direito de Enumerar Serviços Dependentes. No SDDL isso é SW (EnumDeps) na string SDDL. Eu tinha LCRPWP que permite QueryStat, Start e Stop.
O SDDL correto para o Tomcat 6 para mim é:
D:(A;;CCLCSWRPWPDTLOCRRC;;;SY)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;CCLCSWLOCRRC;;;IU)(A;;CCLCSWLOCRRC;;;SU)(A;;LCSWRPWP;;;S-1-1-11-1111111111-1111111111-1111111111-1111)
O mistério é por que o Powershell pode executar Restart-Service de um prompt de comando runas, mas não do Agendador de Tarefas.
Eu obtive a revelação necessária lendo os bits @plattered respondendo ao seu próprio problema similar com Restart-Service em link .