Which apps do that? Do you have a list? Can anything be done about the data after-the-fact?
All these services require either a email or phone number to sign up, so to search for friends who have also signed up for the service, you need to compare two data sets: emails or phone numbers of users you already have, and those in the person's address book.
You obviously wouldn't download your entire database of users contact information to the phone to compare the data sets, so you send the data set up to the server.
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.