I contatti sono sincronizzati con un account Google?
In tal caso va su Google e cancellali da lì: https://contacts.google.com/