Это возможно в двух случаях:
1. Доступна передача зоны (что является ошибкой конфигурации)
2. Для домена настроен DNSSEC
в остальных случаях только брутфорс, т.е. угадывать имена подбором.
newbot: в классической реализации DNSSEС подписываются не только хосты, которые есть в зоне, но и диапазоны имен отсутствующие в зоне, что позволяет дать подписанный ответ NXDOMAIN. По этим диапазонам можно вычислить имеющиеся хосты. Так работает утилита DNSRecon.