Попытайтесь использовать tcptraceroute (или подобный) с целевым портом 80 (или любой другой порт, Вы могли бы думать быть открытыми на удаленном сервере), и посмотрите, как это идет.
Как ring0, сказанный выше, это не проблема DNS - это - маршрутизатор или брандмауэр "там", кто блокирует стандарт traceroute пакеты (icmp).
Here is at least one option for tarpitting these connections after they start spitting out errors. Valid and well-behaved clients shouldn't ever fall into this tarpit.
dnl # New option in v8.14.0
dnl # Override default limit (of 20) NOOPs (invalid or unsupported SMTP
dnl # commands) before daemon will throttle connection by slowing
dnl # error message replies (similar to "confBAD_RCPT_THROTTLE")
define(`MaxNOOPCommands', `5')dnl
You can also use the GreetPause feature, which will reject these clients because they are unlikely to respect the pause. You can read more about it here: http://www.deer-run.com/~hal/sysadmin/greet_pause.html
dnl # New feature in v8.13.1 (not listed in Companion)
dnl # Set time in milliseconds before sendmail will present its banner
dnl # to a remote host (spammers won't wait and will already be
dnl # transmitting before pause expires, and sendmail will
dnl # refuse based on pre-greeting traffic) 5000=5 seconds
dnl # NOTE: Requires use of FEATURE(`access_db') and "GreetPause" entries
dnl # in access table
FEATURE(`greet_pause',`5000')dnl