Li hai cancellati da Google Foto stesso, o dal rullino fotografico del tuo telefono?
Allora, ecco la situazione - le altre risposte vanno nella giusta direzione, ma gli manca una distinzione importante. Quando cancelli una foto nell'app Google Foto, rimuovi solo quella dalla tua libreria Google Foto. Il file originale nel rullino fotografico o nell'app galleria del tuo telefono rimane lì. La sincronizzazione automatica non gliene importa di quello che hai cancellato in Google Foto; semplicemente scansiona l'archiviazione del tuo dispositivo e dice "ehi, questa foto esiste sul telefono, meglio sincronizzarla". Quindi ri-carica tutto quello che trova, anche le cose di cui pensavi di essertene liberato.
La soluzione è cancellare dall'archiviazione nativa del tuo telefono pure - non solo da Google Foto. Accedi all'app galleria predefinita o all'app fotocamera del tuo telefono e cancellale lì. Una volta scomparse dal dispositivo stesso, la sincronizzazione automatica non le troverà più e avrai finito davvero. Potresti anche voler controllare se c'è una cartella tipo "Eliminati di recente" o un cestino in una delle due app che le sta ancora trattenendo; alcuni telefoni mantengono gli elementi eliminati lì per circa 30 giorni prima di rimuoverli definitivamente.
Se vuoi essere extra prudente in futuro, potresti disattivare temporaneamente la sincronizzazione automatica mentre fai pulizia, cancellare tutto quello che vuoi che scompaia da entrambi i posti, poi riattivare la sincronizzazione. In questo modo non c'è confusione su cosa viene sincronizzato dove.