The problem could be that you do not have reverse lookup turned on. However, this may not be an end-all solution. I turned on reverse lookup and it worked for a few months, but some scumbag spammers get smarter and start using open SMTP servers to relay their messages, which will have a valid reverse lookup, but they claim to be someone else like bite-me.com, yahoo.com, etc...
Spam filters will help, but it doesn't solve the issue of bandwidth usage in that your server still receives the entire message and then tries to return a bounce message that most likely gets bounced back to you...
Tom