Did you restart the sendmail daemon after modifying sendmail.cf? Did you modify sendmail.cf or the m4 files and rebuild the sendmail.cf (the better way). There are several recipes that are already built in to the macro files.
Alternately, have you tried using something like spamassassin instead? I'm using it on my mail server and it catches about 85% of the spam. I haven't updated the rules in a bit or it'd probably catch more but I'm not getting enough spam to percolate the update that up high enough on my todo list
Carl