I think I've suggested on a previous occasion that you get an SPF and/or a DKIM record published for your domain. It may well help with Earthlink, and it definitely helps with the Big Three webmail providers.

SPF in particular is a no-brainer, and it certainly won't hurt.

In fact, I've found an old-ish article that asserts that SPF is a must-have for bulk emails: http://www.webmasterworld.com/forum31/2176.htm. It's definitely true for AOL as well.