I suspect what might be happening is a programming logic bug:
1: Photo synced from local device to cloud storage
2: User deletes photo
3: Photos app database marks photo as deleted
4: Photo deleted from local storage
5: Database entry for that photo is removed
6: Command to delete photo from cloud storage fails
7: Command to delete from cloud storage is never checked for success, and so is never re-tried
When update is done, the photos app reconciles the images on the device on the phone and in the cloud to what it knows in the database. Any additional files that aren't in the database are re-added - hence old "deleted" photos reappearing.