Suponho que sua declaração "todos os usuários são" Usuários do domínio "significa que seus usuários não estão executando com direitos de administrador local. Se eles estão, então, consertar isso antes de fazer qualquer outra coisa.
Mesmo que seus usuários estejam executando com contas limitadas, o malware está fazendo um ótimo trabalho com direitos limitados de usuário hoje (melhor do que muitos softwares comerciais, de forma frustrante). Algo como diretivas de restrição de software é a sua melhor aposta para impedir estes tipos de ameaças. É uma corrida armamentista e as empresas antimalware nunca conseguirão acompanhar. Você precisa evitar que executáveis não confiáveis sejam executados - período.
É claro que a política de restrição de software não ajuda muito com o código sendo executado por meio de estouro de buffer / heap, etc. Manter o sistema operacional e o software de aplicativo corrigidos também é uma boa ideia.
Filtrar HTTP, email, etc, do tráfego de rede (com um "scanner de perímetro", etc) para conteúdo executável conhecido provavelmente poderia ajudar, mas os executáveis podem ser obscurecidos em trânsito, então essa não é uma solução geral. O usuário que pegar um pendrive no estacionamento e conectá-lo ao computador também não será detectado por um scanner baseado em rede. A varredura do tráfego de rede é apenas uma defesa profunda.