Я неверно выразился по поводу DNS, извиняюсь. Затыкался tracert сразу после isp на той стороне. Т.е. после isp до конечного mail0.*.ru не доходил. Про dns это я в порыве безумия написал, видимо.
Да, из той же. Затыкается после DNS, стоящего прямо перед mail0.*.ru. Поначалу даже понапрягал админов того сервера, но сделав reload осознал, что проблема у меня.