Как уже писали, юзеров и группы лучше не удалять из AD, а блочить и складировать в спецOUшке. Как раз во избежание подобных проблем.
Если хотите массово почистить ACLs от неразрешающихся SID, можно это сделать subinacl /cleandeletedsidsfrom . Теоретически должно ускорить доступ.
