I have been using a free software and service called Plaxo (www.plaxo.com) and would strongly recommend it. The concept behind Plaxo is elegantly simple. How do you keep your address book with hundreds of contacts current as people change homes, jobs, emails, and phones. Plaxo has a simple solution. It keeps your address book current using a simple process. If the other person is a Plaxo member then everytime he or she updates his address Plaxo will automatically update your addressbook. For all others Plaxo makes it simple to send an email whenever you choose to saying very simply," This is my latest contact information, Here is the contact information I have for you in my address book, can you confirm or update this". Any changes made by the other person is automatically inserted into your address book.
There are several features that Plaxo offers. The one I like best is their address book optimizer which does an intelligent scan of your address book and identify duplicates which you can then get rid of. This service has an annual fee of $29.95. But the clever way in which it cleans up your address book and the time you save makes it worth it.