I’m surprised you cannot use Earthlink’s relay servers and still use your own domain name in the from address. Their goal should only be to block spam from the dynamic addresses, not block all outbound mail, so forcing it to go thru their servers should be enough.
Earthlink may also offer a business-class service for more money that would be unrestricted. Though their service may still suck.
You could research options with your domain-hosting company. Not to endorse any one, but for example GoDaddy’s outlay for the year would be $7/domain and then $10 for 25MB of email storage or $20 for 100MB, and I believe their pop and smtp can run over port 80 and so won’t be blocked. I imagine you can find similar.
For any ISP or domain-hosting, you’d have to check their outbound hourly/daily limits to see if it conflicts with your needs.