I did it with PHP on several sites already, using the following classes to integrate with each service:
Yahoo address book:
http://www.phpclasses.org/browse/package/3127.html
MSN/Hotmail address book:
http://flumpcakes.co.uk/php/msn-messenger
I had some problems trying to grab a gmail address books but this class did it:
http://www.rapleaf.com/apidoc/v2/abook
(I think it's some kind of general class that you can use with any service so it's supposed to integrate with AOL, Yahoo and other providers as well but I'd suggest you try it before deciding).
Also be sure that your site is secured before using any of them, if you will ask your users for their email addresses and passwords you should have SSL and your users have to trust you. Otherwise you will be developing something that nobody will dare to use.