Но! Оказалось, что sendmail (Postfix) письма исправно отправлял, но никто из адресатов их не получал. Проблема в том, что письма возвращались обратно из-за пустого отправителя. Нужно было в конфиге Postfix прописать mydomain и myhostname плюс нужно, чтобы хостер прописал обратную зону для ip-адреса сервера (PTR). После этого письма стали доходить до получателей.