Z informacji, które mi wiadomo Android odwołuje się do kontaktów przypisanych konkretnemu użytkownikowi Gmaila - zaloguj się na pocztę, przejdź do zakładki "kontakty" i tam można zaznaczyć i usunąć (nawet wszystkich) w dosłownie paru kliknięciach - potem synchronizacja do stanu na serwerze... przynajmniej tak to jakoś działało jak miałem Androida
Pozdrawiam