How can I keep a record of user email addresses when users update their email address? I have a site where a minority of users are causing trouble by registering with one email address and then changing to another email address. Email Change Confirmation helps with this, but I would also like to keep a record of changed email addresses per-user, preferably in the Drupal UI.

I am thinking about making an email address field and using rules to automatically add an old email address when the user changes his or her email, but if there is a more robust solution I would love to know about it.
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.