I'm trying to avoid creating my own database of /etc/shadow entries across 46 different servers.

Probably no real way to avoid it. Here's how I solved that problem a number of years ago. Wish I could find the original script, I'd just post it, but here's the psuedocode for it:

if backup of shadow file does not exist:
  a) copy shadow file to backup name
  b) exit
else 
  a) read in shadow file into a hash 
         userid => encrypted password
  b) read in backup shadow file into a hash
         userid => encrypted password
  c) loop through shadow hash
      1) push userid into changed array if 
         password fields do not match
      2) push userid into new id array if 
         userid does not exist in backup hash
  d) copy present file into backup file
  e) email results
[download]

Since everything is kept "local" this can easily be replicated to all the machine you support somewhat painlessly and doesn't require a "database" in the true sense of the word.

If the backup copy of the shadow file doesn't exist, the assumption is that this is the first time the script has been run on a particular machine and no action other than creating the backup copy of the shadow file.

Take care that you preserve permissions such that you don't compromize the shadow file or its copy.

Since Sun first suggested it, you should probably use Pluggable Authentication Modules (PAM). The C example in the documentation (warning, PDF link) shows how to add an extra layer to the password changing process. Your assignment is to wrap the API in XS so that I can use perl to develop PAM plugins ;-) (The PAM stuff on CPAN is only for using PAM, not for extending it.)

Update: Looks like there is already a logging plugin which you can download and compile (tarball link).

Update: You will want logging on the password stack, not the login stack. Other than that, traveler's node probably points you at the quickest (and most perl-y) solution. (++)

You could also use this PAM module to invoke a perl script in your login stack. That script could send the mail.

If that doesn't work, they could use the low tech version of having a cron job compare the current value against the last known value.

Many systems using shadow passwords also record the date the password was changed (as a Julian date in one of the later fields), if your systems have this you could easily figure out who had their passwords changed on a particular day.