Ok, então aqui estão as configurações específicas que eu precisava para fazer isso funcionar:
Host: ims.example.com
Port: 389
User: MYDOMAIN\accountName
Password: *******
Base DN: dc=mydomain,dc=example,dc=com
On-The-Fly User Creation: YES
Login: sAMAccountName
Firstname: givenName
Lastname: sN
Email: mail
O truque foi remover cn=Users
do DN base, depois disso tudo se encaixou.
A outra coisa notável foi a inclusão de um usuário para ler o diretório.
Por último, o usuário que faz login usa seu nome de usuário sem qualificação de domínio e sua senha de domínio como de costume. Nosso domínio não exige um endereço de e-mail, portanto, há uma etapa adicional em que o endereço de e-mail deve ser definido durante a criação do usuário, mas isso é bastante simples.