Проблемы с электропочтой
 

С недавних пор начались проблемы: а именно- с некоторых адресов не проходит почта+ плюс куча спама.
Я из Беларуси -ящик на mail.gomel.by дан в нагрузку к хостингу.
С чем это "непрохождение" может быть связано?

возможно, провайдер банит домены за спам, позвони спроси, если коенечно, это не банальное превышение максимального размера письма или переполнение ящика

Это отпадает точно.

А на счёт провайдера он у нас один -Белтелеком
Может ли быть фильтр за спам на каком-либо промежуточном сервере?
И может ли нормальная фирма (не спам-контора) попать в бан-лист?

И вообще-как выйти из положения? (Без вариантов аренды другого ящика?)

Может. И скорее всего, он стоит на конечном сервере, а не промежуточном.
Может. IP может быть динамическим. При подключении к инету и получения IP адреса, с котрого ранее был разослан спам и этот адрес занесен в бан лист, фирма уже не сможет отправить почту стандартными методами. Еще могут с домена фирмы разослать спам (как целенаправленно людьми так и с использованием вируса) - тоже могут забанить.
Думаю, стоить обсудить данную ситуацию с провайдером, который обязан проверить вашу жалобу.