How can I keep a record of user email addresses when users update their email address?
The first thing that came to mind is Drupal's revision feature. Out of the box, Drupal let's you keep records of what changes are made to nodes over time. Users are a different entity, but the User Revision module aims to provide the same functionality. This Lullabot article explains it pretty well. You could give it a shot.