Tendo estado na situação em que algumas das nossas senhas de clientes foram comprometidas de uma só vez (muitas vezes através de phishing - os idiotas que criam senhas fáceis também são os mesmos idiotas que dariam a quem perguntasse por e-mail), Eu definitivamente diria que é melhor mudar muito somente as senhas que os spammers estão usando (eu as encontrei através do prático cabeçalho Squirrelmail Authenticated User, mas seu webmail pode variar) do que punir todos os 60.000 clientes por as ações de poucos.
Mas parece que você já fez isso ... e não sabe quais são as senhas geradas.
Sua melhor aposta é apenas criar um script de shell que encontre todas as contas de email e, em seguida, altere as senhas para uma cadeia aleatória que ele gera, enquanto cria um arquivo de log de qual endereço de email possui a senha.