А провайдер ни где не мог кислород перекрыть? Может какие-то большие рассылки пользователями производились?
А если на обычном компе (сеть ведь я так понимаю одна), через обычный какой-нибудь почтовый клиент, типа Thunderbird или подобные отправлять и получать почту, работать будет ? Это чисто для проверки, попробовать поработать с Гугловскими, Яндексовскими почтами, своими, чужими, чтобы проверить, туда-сюда работает или нет.