Use a decent spam filter.
The addresses that appear to come from Yahoo are most probably not really originating from there. They are randomly generated, as you observed, and their real origin is a different mail server.
One can always fake the sender's e-mail address, but any reasonably good spam filter will recognize this and categorize the mail as spam. Not to mention that the mail's content will also be identifiable as such too.
As you don't say which e-mail provider you have or which client you use, I can only guess. But Thunderbird has a good spam filter that will also learn based on what you categorize as spam and what you say not. That way any "real" Yahoo mails will never be marked as spam, whereas the fake ones are caught.