Hack the nph-verify.cgi script...
Basically, it would be a matter of integrating the nph-email.cgi script.
One thing you could consider doing is adding a field called Status and then hack the nph-verify.cgi script to update that field in the links.db to 200 (good), 404 (not found), etc.
Then you could simply use nph-email.cgi and select 400 for the Status field, which only target those links that are "bad" and send those link owners a message.
========================================
Buh Bye!
Cheers,
Me