Instead of poluting your otherwise pristine aliases file, include larger files using this syntax:

all_users: ":include:/filename"

This will allow you to email all_users@localhost and get all the users in the referenced file.

If you have a system that might be changing versions multiple times you might orphan some of the lateral utilities (like newaliases). If you want to be certain that you're rehashing the correct aliases file (the one that sendmail.cf is referencing), run sendmail with the -bi option like this:

# /path/to/sendmail -bi