The addresses from the user's address book should be hashed before sending to the server and compared to hashed addresses on the server. Then only positive matches are registered, and the server doesn't see more private information than it needs.
Email addresses can be effectively canonicalized by lower casing. Not many mail servers are case sensitive these days. Additionally, for the local part, you can generally strip off anything after a "+", and with gmail, you can drop any period in the local part. (Granted, it's not perfect-- so make sure that's not a security concern.)
These techniques have been working fine so far in my app for my "Find My Friends" feature.