After speaking with earthlink staff and cross-referencing our logs, it appears this is a situation of easydns (and a few other companies at least) being caught in the crossfire.
A massive spam is going around the internet. Probably everybody with a pulse has received at least a half dozen spam emails promoting penny stock scams (examples: FCYI.PK and CTXE.PK), you may notice half or more have bogus earthlink.net return addresses. They’re all forged, but because of the volume involved, earthlink has now blacklisted us and others for the number of these spams we’ve bounced back at them as invalid.
It’s basically a big “backscatter” storm, we’re implementing filters to try and strip out most of these messages, it should have the effect of automatically removing us out of the earthlink filters at some point.
Keep in mind at the moment, legit email is stuck or delayed, it is not being lost or bounced.
We’re still trying to accelerate a whitelisting process with earthlink, more as it comes in.