OT: Dumb mail question

I am using a new dial-in drop for my network connection, and a somewhat
unfamiliar mail handling system (postfix) on my local computer. A large
amount of outbound mail is getting returned because the recipient
machine is not found (these include such obscure names as redhat.com :/

Anyway, I'm going to try to install sendmail this weekend to see if it
fixes the problem, but in the meantime does anyone have a suggestion for
a "relay machine" I could try using? Most machines nowadays reject relay
requests, but perhaps there is a "known relay"? btw, I have postfix
configured to *not* verify dns on mail (and currently to *not* use a
relay), and the problem seems to be coming from farther along the chain.

TIA for any suggestions.

- Thomas

btw, I've got DSL on order, so hopefully these problems will go away in
a month or so...