Sendmail catch-all alias doesnt' work anymore?

[questions at geektank.org]

I'm trying to figure out why my sendmail catch-all alias does not work.  i
have:

@mydomainname.com	myusername

as the last line in my /etc/mail/virtusertable and I did rebuild the
virtusertable db by running:

makemap -r /etc/mail/virtusertable < /etc/mail/virtusertable

I try to send a test message to some random email address that doesn't
exist and it gets bounced by my mail server saying user doesn't exist.

I tried testing the mapping out by running "sendmail -bt" and doing this:

---
# sendmail -bt
ADDRESS TEST MODE (ruleset 3 NOT automatically invoked)
Enter <ruleset> <address>
> /map virtuser randomname at mydomainname.com
map_lookup: virtuser (randomname at mydomainname.com) no match (0)
---
(note: i'm replacing my real domain name with "mydomainname.com" for this
email).

If I add the randomname at mydomainname.com to virtusertable and rebuild the
db emails and mapping work fine.

Any tips on how to properly diagnose this?