Какие-то странные глюки с почтой...

Здрасьте Господа! Проблема определенно существует, но какая-то она расплывчатая. Но иногда в логах сендмыла появляется запись, что исходящее письмо вроде как accepted for delivery, но человек по аське или телефону, говорит, что ни фига не получал, или получил через несколько часов после записи в логе. Плюс юзвери периодически жалуются на входящую почту, мол не приезжает, при том только с некоторых адресов. Сколько не посылаю себе тестовых писем с разных yahoo, mail.ru, hotmail и т.д. - приезжают тут же. А потом через пару дней те же юзвери приходят и говорят что только сейчас приехало. Мой dns в порядке. Провайдеру что ли морду бить? Что присоветуете? Всем ответившим заранее спасибо!