В сендмыле есть встроенные средства (проверка входящей почты на DNS-адреса, занесенные в антиспамерские базы). Я проверяю по dnsbl.njabl.org, relays.osirusoft.com и всех dsbl.org. Отсеивается примерно 70% спама. Маловато, но что поделать.
DNS это конечно хорошо, но мне кажется не серьезно, тем более в виду (возможно чрезмерной) паранои мне как-то не хочется доверять разным спискам адресов, себе я больше доверяю :-) (хотя может я и не прав)
Борьбой со спамом особо не занимался (не было надобности), но могу порекомендовать посмотреть такой продукт, как spamassasin (+spammilter, если надо связывать его с sendmail).