La clave para solucionar el problema es que las fotos borradas siguen ocupando espacio de almacenamiento en el teléfono hasta que realmente las borras. Windows tiene la papelera de reciclaje. Mac tiene la Papelera. La aplicación Fotos de iOS 8 tiene su propia variante de la papelera que sólo se aplica a fotos y vídeos.