As far as I recall milters get executed in the order they're defined. i.e. InputMailFilters=milter1, milter2, as do all rules in the sendmail.cf configuration file.
I has been ages since I last configured sendmail and that was always a complete PITA for all things not standard (and even then). As far as I remember sendmail would not check the existence for a recipient immediately, but if the domain is local would accept the message during the SMTP dialog and then do further processing and send a bounce later if the specific user is found to be invalid. That might be the reason your milters get executed even for invalid recipients.
For from ideal, but your best bet might be to enable the blacklist_recipients as IIRC that is a test that gets performed during the SMTP dialog and should prevent the message for named invalid recipients from getting accepted in the first place. Sendmail should reject mail for thus addresses during the SMTP dialog and not do any further processing all:
FEATURE(`blacklist_recipients')
then you can add entries to the access map for local users and/or addresses in your domain, where the user has been deleted and which should no longer receive mail:
badlocaluser@ ERROR:550 Mailbox disabled for this username
[email protected] ERROR:550 Mailbox disabled for this username
That adds some overhead as you need to both disable user accounts as well as "document" them as deleted in the access table.
