На прием и отправку -- это разные почты. Прием работает откуда угодно, а отправка (в целях борьбы со спамом) требует специальной настройки (указания в почтовом клиенте интернет-адреса SMTP-сервера провайдера связи). Т.е. если ты вдруг поменял провайдера интернета на своем компьютере, то тебе нужно поменять эту настройку (все провайдеры ее сообщают специально).

Это не относится к веб-почтам (которые работают через браузер, типа yahoo.com или mail.ru).

Да. Пришлось провести маленькое служебное расследование.
Оно вывело на некий полицейский сайт под названием www.spamcop.com
Этот сайт арестовал IP-адрес моего дурацкого провайдера. "Дурацкого" - т.к. у них один адрес на всех пользователей локальной (домовой) сети. О спаммерах у провайдера слышали и сказали, что "в принципе, боремся". О полицейском spamcop'е - не слышали, пошли по ссылке и в трубке довольно долго раздавалось: "вот это да! ну и ну! ух ты!". На просьбу позвать кого-нибудь из старших, представители провайдера заверили, что старшие придут завтра и будут разбираться.
Так что, либо через 48 часов эти электронные полицейские снимут свой замок, либо старшие специалисты провайдера устранят неполадки. Третьего - не дано.

Грубо говооря, каждое письмо дважды пересылается от компьютера к компьютеру: сначала почтовая программа отправителя (например, The Bat) пересылает его SMTP-серверу, который указан в её настройках, во второй раз этот SMTP-сервер передает его сереру получателя, который определяется по email-адресу получателя. (А потом уже почтовая программа получателя скачивает полученное письмо себе.)

По Вашему тексту у меня сложилось впечатление, что проблема возникает на первом этапе. Это довольно странно, потому что особого смысла проверять по spamcop'у письма своих пользователей нет. (spamcop же, строго говоря, ничего не блокирует, он только предоставляет список IP-адресов, по которому почтовые сервера могут проверять письма, если захотят. Причем идея в том, чтобы проверять именно получаемые письма,а не отправляемые.) Так что можно попробовать связаться с владельцами этого почтового сервера и попросить их не проверять spamcop'ом отправляемые письма или сделать исключение для Вашего IP. (Если же владелец этого почтового сервера -- та же самая домовая сеть, то это в высшей степени глупо с их стороны). Можно также попробовать воспользоваться каким-нибудь другим SMTP-сервером, например тем же сервером домовой сети.