You should definitely check out ContactRescue (formerly Flashback, a one-time service that analyzes your past emails to massively update your address book overnight. You can analyze up to 20,000 emails with ContactRescue and up to 60,000 with a ContactRescue +.
To run ContactRescue, first go into the ContactRescue tab in your settings and purchase the one that is suited to your needs.
Once you have purchased ContactRescue, you can run it by going back into the ContactRescue tab in your settings and doing the following:
1) Select the Folder you want the ContactRescue results saved in, and check the box if you want the phone numbers of your contacts internationalized:
(NOTE: The folder you choose in this step will become the default folder for contacts Evercontact finds for you. If you’d like to have your ContactRescue results saved in a separate folder, be sure to go back into your settings and change your default folder. Instructions on how to change your default folder can be found here.)
2) Select the folders you want to analyze.
3) When you have selected all of the folders, click launch.
Your ContactRescue will usually take under 24 hours to process, and once it has finished, you will receive an email notifying you of the results. The results will also appear in the ContactRescue tab of your settings.