Existem alguns métodos disponíveis para fazer isso. Eu não tive boas experiências tentando randomizar este programaticamente - tentar escrever qualquer coisa, mas um 0 ou -1 para o atributo pwdLastSet não funcionou para mim.
Minha tendência seria aplicar sua nova política de senha e expirar as senhas de um grupo de usuários semanalmente para distribuir a carga.
Você pode usar admodify para redefinir a data da última modificação. Eu pegava um grupo (na verdade eu importava uma lista de nomes de usuários de um arquivo TXT) e exigia que eles mudassem sua senha no próximo login.
Mantive uma planilha para saber quais usuários ainda precisavam expirar.
Duas desvantagens para essa abordagem - você precisa executar esse script várias vezes e os usuários não obterão o uso completo de seis meses da primeira senha complexa.