*@mydomain.com worked fine for me for about 15 years, then suddenly spammers started doing exactly that, sending e-mails to random addresses. I would get countless copies of every spam message, addressed to completely random combinations of characters @mydomain.com.
