I run a forum ( http://forum.starmen.net/ ) that has a traditional signup, and more importantly, password recovery, that requires your email address. The problem is that a lot of ISPs, including AOL and BellSouth, just plain do NOT accept our emails. For example, this is from a direct TELNET connection to AOL: http://pastie.org/275370 . Our emails are just plain not allowed in, and it's frustrating having to do automatic password recoveries without email addresses.
I'm not doing anything illegal, just sending a "Welcome to our Forums!" email and password recovery upon request. Our email ( http://pastie.org/275373 ) contains both a real address and an opt-out page, which is what most filters look for. Gmail and Yahoo work fine, some ISPs work fine as well as SpamAssassin based stuff, it's mostly AOL and small ISPs.
How do you get important information around overzealous spam filters?
Setup a for-real MTA, with proper forward and reverse DNS (and likely SPF) records. Then, send your emails through that MTA. If you're still getting rejected, try some variants of your message and text-content to URL ratio, etc. until you find what works reliably.