The e-mail programs (online) could automatically advise the user to delete the e-mail address from their contacts list if it comes back as a Delivery Status Notification (Failure). The e-mail provider could also provide an option to send a letter in the U.S. Postal Mail on behalf of the user requesting an update to the e-mail address, using the physical address, or addresses listed in the contact information.
There could also be a registry online, that people with old e-mail addresses could register a forwarding address, even after they no longer have that ISP, so that people know how to get in touch with them in the future if they try to contact them at that e-mail address.