Bem, eu percebi. Deixando a resposta aqui e alguns outros lugares para as futuras gerações:
O sistema não tinha o pré-requisito "secreto" de ter Visual C ++ 2010 x86 redistribuível instalado (não o x64, aquele que tinha). Corrigido o problema instantaneamente.