на мэйле, то испытывал аналогичные проблемы. С яндексом вроде до сих пор работало. Трудный вопрос - почему? Про другие почтовые агенты ничего сказать не могу. Ведь порой спам-фильтры работают не по конкретым адресам, а по некоторым символам в письме. Кроме того, у многих почтовых агентов есть внешние общие ля всех спам фильтры по DNS, а у данного хостера он один на всех и мог попасть в этот спам фильтр.

С уважением