>может есть еще варианты?
Сеть состоит из подсетей вида 10.1.1.0/24 ., 10.1.2.0/24 etc ?
Или это адреса из "большого" Интернета?
Для интранетовских адресов у меня используется до безабразия тупая схема с отдельно стоящим DNS сервером, который берет обратные зоны (slave) с нескольких локальных мастеров, где регаются клиентские win машинки (DHCP,DDNS).
gethostbyaddr() использует только этот отдельно стоящий DNS сервер и работает довольно шустро, т.к. этот DNS сервер умеет кешировать записи, а на не существующие - выплевывает SERVFAIL.