Olá Thiago.
Desculpe a demora em responder, mas não recebi o alerta do fórum de que houve uma resposta.
Quanto a sua pergunta, sim, todas as informações de que preciso continuam cadastradas nas contas dos usuários no AD.
O fato é nem mesmo se pesquisar pelos campos de primeiro ou sobrenome, nem mesmo o DisplayName trazem resultado.
Descobrimo pouco tempo depois da postagem inicial, de que são apenas alguns usuários que estão com este problema, mas não conseguimos determinar algo relacionado a eles (alguns XP, outros são Windows 7, etc).
Grato,
Filipe