Попробуйте забодать своего провайдера на предмет правильного Reverse DNS lookup.
Без этого, большинство майл серверов вас бортанут.
Это вроде минимального антиспама.
Приличные провайдеры, обычно, разрешают пользоваться своим mail relay.
Тогда, в Exim надо будет прописать "Smart" relay host.
Если вас устраивает, что весь майл будет отправляться от имени одного пользователя,
сделайте аккаунт, например на google и отправляйте майл через него (
настройка Exim для google)
или найдите другой фришного провайдера.
Или, например исходяший майл трафик через TOR завернуть.
У TOR-а реверс работает, правда некоторые майл сервера, его тоже порежут.
Слишком много спам-а расплодилось, в результате антиспам тяжко страдает паранойей