Supondo que seus clientes não estejam com o Power of PowerShell, sua única outra opção (dado que a Microsoft não se preocupa em corrigir o comportamento de pesquisa) é acessar os registros DNS com um cliente diferente que classifica como eles querem isso.
Uma forma é exportar a lista para um tipo de texto delimitado e usar o Excel para classificar a maneira que eles gostam (o que é mais esforço do que eu gostaria de investir).
A outra maneira, que eu provavelmente preferiria, é usar um sistema operacional cliente diferente. Você pode usar o Gerenciador de DNS para conectar um servidor remoto e, se o cliente em questão for o Servidor 2003, Windows XP ou Windows 7 32bit o comportamento de pesquisa é o tipo que eles estão querendo. Portanto, eu recomendaria girar uma VM ou estação de trabalho Windows 7 de 32 bits, instalando o pacote RSAT e direcionar seu cliente para usá-lo para fins de gerenciamento de DNS. Parece-me ser a maneira mais fácil, menos disruptiva de obter do seu cliente o que eles querem.