Pienso que si tienes contactos que están sincronizados y otros no, lo mas seguro es que están en la SIM Card. Hay muchas app para copiarlos desde allí, pero en ocasiones, he tenido que usar el software del teléfono para extraerlos, o hacerlo en un móvil antiguo... Si das mas información de teléfono, rom actual y demás tal vez podamos ayudarte.
NOTA: Si los borraste del teléfono, también se borraron de tu cuenta de google (sincronizacion en dos vias), independiente de que rootearas o pusieras otra rom