Ummm... why not just switch providers. Acually I guess the question is, how cheap is cheap? Where I live Juno/Netzero uses local providers for their access numbers and connectivity. Most local providers will sell you dial in anywhere from $10 - $20 a month. What is wrong with that?

Also it could be whoever owns the SMTP server you were using has denied relaying. Most SMTP servers do this now. IE you have to be in their IP range to use the server...

I don't know if that helps or not maybe I'm misunderstanding the problem