I do not think that there is "one way" to fix this (if there were, then it would be easy for spammers to go straight to inboxes) Reverse DNS (ip mail domain)

I do not think that there is "one way" to fix this (if there were, then it would be easy for spammers to go straight to inboxes) Reverse DNS (ip mail domain) SPF Record Sender ID 3rd party verification (goodmail systems is one example linked from aol's spam abuse) - they are $400. 80k sounds like a little bit too much Apply to be "whitelisted" at each specific provider (http://help.yahoo.com/fast/help/us/mail/cgi_bulkmail http://help.yahoo.com/fast/help/us/mail/cgi_bulkmail is yahoos, aol has one) Switch MTAs (postfix, sendmail, qmail) - try alternating Make sure your headers make sense and are valid (reply-to,return-path, from, message-id, etc) Finally, send email people actually want. It seems that the systems are somewhat automated (aol is for sure) to reject mail if a certain % of users flag it as spam.