Ты ж моа, ну.

Не у большинства, у всех. Абсолютно все подобные сервисы используют базы, порой передирая их друг у друга. Со временем они научились составлять их поумнее, чем просто резолвить все подряд. Но иных вариантов, все же, не так много. Они могут делать трансфер зоны у нейм-серверов, могут резолвить запросы юзеров и тут же добавлять их в базу, могут делать обратный in-addr.arpa резолв. Но суть одна - все они так или иначе достают домены\адреса и резолвят-резолвят-резолвят. Самые хитрые за деньги предоставляют самую мякотку - историю ns\mx серверов и данных whois, порой за многие годы. И оно того стоит.