I know this is an old thread, but I had the same problem just recently.
I did not ask if SBC/Yahoo blocks port 25, but I did get the system to send mail to external addresses by editing the "smarthost" line in the sendmail configuration.
I managed to find out the smtp server (for me at least) is smtp.prodigy.net. Modifying the appropriate line in /etc/mail/sendmail.mc made everything work again.
This was on an FC4 machine, and the exact steps were;
1. Uncomment the line in /etc/mail/sendmail.mc (by removing the dnl from the front of the line)
2. Replacing "smtp.your.provider" with "smtp.prodigy.net"
3. running "make -C /etc/mail"
4. restarting sendmail with "/etc/rc.d/init.d/sendmail restart"
Just giving the solution in case anyone else might need the answer and comes across this post.