Depois de bater a cabeça contra a parede por algumas horas, encontrei uma solução. Parece que no Server 2012, as tarefas agendadas não podem tocar em diretórios que não têm permissões de permissão explícitas para a conta que você está usando para executar o arquivo. Não importa se essa conta está em um grupo que é permitido no diretório.
Por exemplo, se eu quiser rodar o E: /stuff/target.exe usando a conta THINGS \ svcAccount, então THINGS \ svcAccount deve ter um controle total explícito sobre E: / stuff para executar . Eu tinha assumido que, se THINGS \ svcAccount estivesse no grupo de administradores, e o grupo de administradores tivesse controle total sobre E: / stuff, herdaria permissões. O Server 2012 não faz isso.
Isso só parece se aplicar a tarefas agendadas - executando uma janela de comando ou uma janela do powershell, pois THINGS \ svcAccount funciona exatamente como esperado.