Если Verizon делегировала PTR к Вашему серверу имен, она должна работать во всех случаях.
Можно всегда проверять делегацию PTR путем запросов базы данных ARIN по http://www.arin.net и проверки, что нет других записей NS на зоне делегации (который мог быть, почему иногда она не работает).
Если это - недавняя делегация, это могло бы произойти также из-за кэширования, проверить базу данных ARIN, ожидать в течение нескольких дней в случае необходимости :)