Hmm, that might be a clue for me. When I put in a new alias, I manually "makemap hash virtusertable < virtusertable.txt". If the sendmail upgrade runs a Makefile to do its own virtusertable.db rebuild then it's possible it uses other sources, or "makemap dbm" instead of "makemap hash". That could explain the screw-up.
It indeed uses /etc/mail/Makefile to rebuild maps.The first thing I do after an upgrade is to edit the Makefile to remove the at-signs on the front of the commands so that I can see what gets made. If there's interest in making this edit in the package, I can file a bugzilla and supply a patch.