Простой способ — не валидировать пользователей локальных доменов совсем (хоть это и не так сложно). А:

1. (В принципе, опционально.) Настроить SPF.

2. Отвечать всем, кто пытается тебе скормить письмо с твоего домена, но не является твоим релеем или клиентом, сказавшим SMTP AUTH, «5xx пшёл вон».

...про envelope from. Если ты про хедеры письма, придётся немножко попотеть. Но надо ли оно тебе?

Прошу прощения за дубликаты.

> Но надо ли оно тебе?

Да спамеры запарили. Наблюдаю, что таким образом можно приличную часть спама отсечь.

Кир, я всё-таки спрошу ещё раз. Ты точно про message from, а не про envelope from?

(У меня какбе есть статистика на эту тему, которая говорит, что спаммеры используют именно envelope from.)

Да вроде и там и там один и тот же адрес.

Вот хидеры письма:

Received: from 109.Red-88-19-114.staticIP.rima-tde.net (109.Red-88-19-114.staticIP.rima-tde.net [88.19.114.109])
	by vzorg.swsoft.net (8.13.1/8.13.1) with SMTP id mALEVCJH001970
	for <devel@openvz.org>; Fri, 21 Nov 2008 09:31:13 -0500
Received: from [88.19.114.109] (port=34220 helo=109.Red-88-19-114.staticIP.rima-tde.net)
        by openvz.org with esmtp 
        id c14819-d5bcf6-fe
        for devel@openvz.org; Sat, 22 Nov 2008 15:28:26 +0100
Message-ID: <4928170A.40500@openvz.org>
Date: Sat, 22 Nov 2008 15:28:26 +0100
From: "Carol" <hklscxi@openvz.org>
User-Agent: Thunderbird 2.0.0.9 (Windows/20071031)
MIME-Version: 1.0

Nov 21 09:31:14 vzorg sendmail[1970]: mALEVCJH001970: from=<hklscxi@openvz.org>,
 size=1057, class=0, nrcpts=1, msgid=<4928170A.40500@openvz.org>, proto=SMTP, da
emon=MTA, relay=109.Red-88-19-114.staticIP.rima-tde.net [88.19.114.109]

Вот именно поэтому фильтруй по envelope address.

Это тупо легче. (Задача может свестись даже к «настроить SPF».)

Я бы порекомендовал поработать над регекспами для отсечения динамических хостов по имени. Хотя бы для таких распространённых случаев, как приведено выше.