Все правильно получаете, кодировка тут не при чем. Согласно спецификации "DNS Packet Structure", вы получаете не строку, а пакет который нужно разобрать. К примеру если запрос будет "nslookup www.google.ru 127.0.0.1", то там где вы получаете имя хоста будет строка "''#3'www'#6'google'#2'ru'#0#0#1#0#1".
Парсинг простейший:
#3 - означает что далее идут 3 символа хоста
'www' - вот ожидаемые 3 символа
#6 - далее идут еще 6 символов хоста
'google' - ага, вот они
#2 - ну и еще 2 символа
'ru' - ура, они здесь
#0 - конец имени хоста, складываем в кучу, перемежая точками и получаем www.google.ru
#0 - дальше у нас служебная информация...
#1
#0
#1
Вот как то так.
P.S. А зачем вам на таком низком уровне работать? Может использовать IdDNSServer : TIdDNSServer ?
P.P.S. Правильно Memo1.Lines.Add(BytesToString(AData,12)); //(12, а не 13)