I have been having the exact same problem for about a month now.
We have the "secure email" option enabled (if not, this wouldn't be a problem).
Originally, it was ONLY when a member having a yahoo.com email address attempted to send an email to another user. It doesn't matter what the receiver's email address is...what makes it bounce back is when the SENDER'S email address is a yahoo.com email address.
More info on why can be found here:
http://marketingland.com/email-sende...emailmarketing
For about the past week or so, I have started to see aol.com email addresses (SENDER) get rejected for the same reason.
I too am hoping for a good solution to this...if nothing else, simply reject the email attempt at the "send" stage so the member knows immediately their email didn't go though (I already have a bold red large text notification in the email interface, but again...many users seem to overlook it (somehow) and submit their email anyway...