Acontece que eu era insuficientemente atento, excessivamente paranóico, ou talvez um pouco ... BOFHy quando defini as políticas de senhas refinadas. Olhando atentamente para eles (ADSI edit não é uma ótima interface para isso, muitas outras coisas) notei que estou definindo uma idade mínima para a senha.
Aparentemente, as redefinições administrativas realmente redefiniram esse cronômetro de envelhecimento para zero.
Aparentemente, o Windows relata o erro de complexidade de senha quando é muito cedo para redefinir uma senha.
A menos que eu queira mudá-lo, meu "me restaure!" os usuários terão que aturar (por exemplo) 2 dias do dunce-cap impossível de lembrar-mas-muito-longo-senha antes que eles possam configurá-lo para algo que eles possam lembrar.
Talvez este seja apenas o martelo que preciso para convencê-los a criar contas de domínio.