Disable group policyn som är satt på dem så ser du om det börjar fungera efteråt.
Du får nog gå igenom dina inställningar en gång till.
Du kanske har satt på att de inte får köra program som inte är granskade på nått visst sätt?

Kolla så maskinen finns med i AD också, så ingen har tagit bort den.

Edit:
Testa kör detta program: dcomcnfg.exe

/Mami