zuborg
напиши скрипт который будет запрашивать их у корневых dns серверов той зоны которой принадлежит домен (например *.gtld-servers.net для com/net)
если они не знают про такой домен - значит незареган (или в процессе регистрации, залочен etc)
geCTP
whois'ом будет дольше, и вроде можно получить бан от хуиз сервера, за частое обращение
простым резолвом можно отсеять зареганные домены, а потом их уже whois`ом пробивать на зареганость