I decided that it might be something getting hung with that particular server. Our ISP (as with most big ones, I'm sure) will load balance across several physical machines, so smtp.earthlink.net might resolve to quite a few different addresses over time. OS X caches these addresses. So the fix seems to be to get the cache flushed and hope for a different machine. It's worked for us the several times we've tried it.
Using info from previous hints about how to call a shell script from AppleScript, and a command from this previous hint (I used the command from the first comment) to actually flush the cache, I've come up with the following solution. Put the below command in an AppleScript, and put the script in your Library -> Mail Scripts folder, refresh the scripts menu and you're ready the next time it fails.
do shell script "lookupd -flushcache"

