Use postfix...
I had a similar 'attack' a few months ago. I thought I ran a pretty tight ship but I was proven wrong. Firstly, I'd suggest running postfix instead of sendmail; It has far more easy-to-configure features for staving off attacks like these (such as anvil). I had to block the backscatter to the fake <never used addresses>@mydomain.com using the following lines. In my case the mails were not coming from any common source IP block (i.e. it was a DDoS) so I had to block on the targeted fake recipients:
smtpd_recipient_restrictions =
permit_mynetworks
permit_sasl_authenticated
reject_unauth_destination
check_sender_access hash:/etc/postfix/sender_whitelist
check_sender_mx_access cidr:/etc/postfix/mx_access
check_recipient_access hash:/etc/postfix/recipient_block
reject_unknown_recipient_domain
reject_rbl_client zen.spamhaus.org
reject_rbl_client bl.spamcop.net
/etc/postfix/recipient_block contained the following (e.g.):
fakeuser@mydomain.com DISCARD
fakeuser2@mydomain.com DISCARD
This rejects and effectively blackholes these emails while dropping the client connection at the earliest opportunity without causing any more error emails. It does seem that the attack attempts have now gone away. I was getting hundreds per minute before.
PS: I have a load of other settings to prevent spammers (none actually examine the email body) and as a result I get next to no spam (< 10 a year) on all of my 10 active email domains.