I had this problem for several weeks, and I'm documenting it in case anyone else is unlucky enough to be in this situation and needs to find the solution. I was seeing that Earthlink and Mindspring were not able to send to my domain. The senders would get delivery delay emails and the delivery failures eventually on all emails to my domain. With a couple exceptions, everyone else had no problem sending to my domain. So 99% of all email was coming through, but these couple were problematic.
It turns out that I had configured too many real time block list providers (RBLs). When the remote server was connecting to my server, the process of checking the sending server against all 5 RBLs would take some time. In this case, the Earthlink servers wouldn't wait long enough for my server to finish checking - and the Earthlink servers would drop the connection. The solution was to just have one block list provider. In this case I used zen.spamhaus.org
So that was it. Just a note for future reference.