there should be an error number associated with that error, if
it's a 500 error it's most likely a relay access block issue. (550
relay denied, etc). In this case your going to want to check the
blacklists at www.spamhaus.org.
What it really looks like is a poor connectivity problem, your mail
server could be trying to send too much information at once, or
you may have an issue with connectivity or latency. Whats kind
of link is this server connected to, and how is dns set up? Is
there reverse dns set up? Sometimes if there is no PTR record
other mail servers will immediately assume you are a spammer
and drop (while I havent seen it with yahoo it is possible)
check this by running nslookup in a command prompt and then
issuing the following:
set querytype=PTR
then type in the mail domain (just domain name, no hostname
or mail.)
mydomain.com
if it returns an answer you've got PTR records, if not you may
want to contact your ISP about gettng those put into place.