Пожалуйста, порекомендуйте компанию-хостера, которая может оказывать следующие услуги в следующем объеме:

1) Предоставление почтового сервера для входящей почты.
У нашей фирмы имеется 5 доменов (например firma1.ru,...,...,...,firma5.ru). Вся почта с этих доменов должна поступать на сервер компании-хостера (MX-записи для доменов перенастроить не проблема).
На сервере компании-хостера почта проходит проверку на вирусы и на спам по RBL, непрошедшая почта уничтожается, но в логах сервера отражается факт ее прихода. Оставшаяся почта проходит проверку на спам по эвристике, непрошедшая проверку почта помечается в заголовке тэгом X-Spam или подобным.
Затем почта направляется на внутренний почтовый сервер нашей фирмы (через ETRN). Желательно, если сервер хостера будет передавать почту серверу нашей фирмы по SMTPS или VPN.
Если сервер нашей фирмы в данный момент недоступен, почта должна храниться на сервере хостера не менее 1 месяца с момента прихода.

2) Предоставление релея
Вся исходящая почта нашей фирмы перенаправляется на сервер хостера, который и будет заниматься ее доставкой. В этом случае также желательно соединение серверов по SMTPS или VPN.
Желательно, если сервер хостера перед отправкой сможет вычищать из заголовков писем все тэги, в которых есть упоминания о сети или внутреннем почтовом сервере нашей фирмы.

Ежедневный объем почтового трафика :
Входящая почта - до 100 МБ (примерно 1-2 тыс.писем, больше половины из которых как правило спам, который надо отсечь еще у хостера)
исходящая почта - до 30 Мб (100-300 писем)

Основные требования предъявляемые к компании:
1) Техподдержка 24х7 при минимально возможном времени устранения неполадок если таковые возникнут
2) Своевременное обновление антивирусных баз и спамфильров
3) Своевременное отслеживание появления ip-адреса почтового сервера хостера в RBL и незамедлительные действия техподдержки по исключению данного адреса из RBL
4) Предоставление доступа к логам почтового сервера.
5) Квалифицированный персонал техподдержки, способный проконсультировать по всем вопросам, связанным с установкой, настройкой и устранением неполадок в работе почтовых серверов по данной схеме.

Вариант co-location'а и вариант прямой доставки почты на внутренний почтовый сервер фирмы не рассматриваем.

P.S. И все это за приемлемую цену (не более 100-150 у.е. в месяц)

Подозреваю, что с учетом полтинника RBL за IP плата может показаться провайдерам недостаточной.

Сделать это не сложно и легко для хостера а вот антиспам система грамотная это сложно, использовать RBL и эвристику можно, но это не все равн оне самый лучший вариант.

Я например хочу заюзать http://so.yandex.ru/companies/price.xml
но пока цены кусаются.

Можно взять VDS, настроить там нужный софт или заказать настройку у специалиста.
Как TCO будет где то 100-150, с учетом единоразовой настройки.