Задачка по sendmail.cf

Я тоже не большой знаток, но мне кажется, что "_" в данном случае не
является лексемой. В правилах должны указываться лексемы (что это
такое и какие бывают - смотреть доки, citforum.ru,...), а "_user"
оно похоже интерпретирует не как 2 лексемы "_" и "user", а как одну
- "_user", которая соответственно никак не равна "_".

А сделать можно попробовать так: заставить sendmail интерпретировать
"_" как разделитель (delimiter):

# delimiter (operator) characters (old $o macro)
O OperatorChars=.:%@!^/[]+_

Из citforum.ru:
Набор "операторов" в адресах. Список знаков, которые могут быть
рассмотрены как обозначения, и которые будут разделять значения во
время анализа. Например, если "@" было в макросе $o, то ввод "a@b"
будет просканирован как три обозначения: "a," "@," и "b." По
умолчанию ".:@[]", минимально необходимые для анализа по RFC 822;
более богатый набор операторов - ".:%@!/[]", добавляющий поддержку
для UUCP, %-hack, и адресов X.400.

Тогда переписать так:
R$* $={badchar} $*                   $#error $@ 5.7.1 $: "SPAM"
или лучше как минимум для 2-х вхождений :
R$* $={badchar} $* $={badchar} $*    $#error $@ 5.7.1 $: "SPAM"

ДА,так оно и есть.
Для тех, кто пойдет по моим стопам, вот пример антиспам-фильтра на основе regex
для sendmail www.anrb.ru/linux/regex.html